[알고리즘 도론] 2.3-7

12879 단어 독서 노트

[알고리즘 도론] 2.3-7


n개의 원소의 집합 S와 x를 정하여 두 원소가 S에 속하는지 판단하고 그들의 합은 x로 시간 복잡도를 요구한다Θ Θ Θ(nlgn)。


우선 정렬, 시간 복잡도Θ Θ Θ(nlgn) 그리고 두 표병을 설치하여 가장 작은 곳과 가장 큰 곳에서 서로 앞으로 나아가게 하고 매번 두 원소와 x를 계산하면 정지한다.x보다 작으면 작은 표병이 전진한다.만약 x보다 크면, 대표병이 후퇴한다.두 표병이 만나거나 x의 두 원소를 찾을 때까지.시간 복잡도Θ Θ Θ(n) 총 시간의 복잡도는Θ Θ Θ(nlgn).
코드는 다음과 같습니다.
/*  2.3-7*/
#define _CRT_SECURE_NO_WARNINGS
#define MAXN 3200
#include
int ans = 0;
void merge(int a[], int p, int m, int q)
{
	int t, i, j, L[MAXN], R[MAXN], n1 = m - p + 1, n2 = q - m;
	for (i = p; i <= m; i++)
		L[i - p + 1] = a[i];
	for (i = m + 1; i <= q; i++)
		R[i - m] = a[i];
	L[n1 + 1] = R[n2 + 1] = MAXN;
	i = j = 1;
	for (t = p; t <= q; t++)
	{
		if (L[i] <= R[j])
		{
			a[t] = L[i];
			i++;
		}
		else
		{
			a[t] = R[j];
			j++;
		}
	}
	return;
}
void cal(int a[], int p, int q)
{
	int m = (p + q) / 2;
	if (p == q) return;
	cal(a, p, m);
	cal(a, m + 1, q);
	merge(a, p, m, q);
}
void main()
{
	int x, n, a[3200], i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &x);
	cal(a, 1, n, x);
	i = 1;
	j = n;
	while (i < j)
	{
		if (a[i] + a[j] == x)
		{
			ans = 1;
			break;
		}
		else if (a[i] + a[j] < x)
			i++;
		else
			j--;
	}
	if (ans)
		printf("yes
");
	else
		printf("no
");
	getchar();
	getchar();
	return;
}
블랙과 isort의 설정이 충돌할 때 처리하는 방법
방법: AWS Amplify의 자동 채우기 스키마 필드

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage