오름차순 배열에서 입력 숫자 n과 같게 두 수를 선택합니다.

1515 단어 인터넷면접 시험null

제목 설명


이것은 한 인터넷 회사의 면접 문제로 승차순으로 정렬된 수조와 하나의 숫자 n을 입력하여 수조에서 두 개의 수를 찾아 그들의 합이 그 입력 숫자 n과 꼭 같도록 요구한다.만약 숫자의 합이 n과 같으면 임의의 쌍을 출력하면 된다.

소박한 해법


두 변수 i와 j를 사용하여 두 층의 순환을 이용하여 수조를 훑어보고 데이터 [i]+데이터 [j]가 입력 숫자와 같고 i가 j와 같지 않을 때 데이터 [i]와 데이터 [j]를 출력하면 원하는 두 개의 숫자를 찾을 수 있다.다음은 이 해법의 코드입니다.
void find1(int *data,int num)
{
	assert(NULL!=data);

	int i=0;
	int j=0;
	for(i=0;i<len;i++)
		for(j=0;j<len;j++)
			{
				if((i!=j)&&((data[i]+data[j])==num))
					{
						printf(" %d + %d = %d  
",data[i],data[j],num);
						return;
					}					
			}
	printf(" not find them  
");
	return;
}

이런 해법의 시간 복잡도는 o(n^2)이고 승차수조라는 조건을 충분히 이용하지 못했다는 것을 쉽게 알 수 있다.

더욱 합리적인 해법


우리는 두 변수로 수조의 첫 번째 원소와 마지막 원소, 즉 수조의 최소값과 최대값을 찾을 수 있다.이 두 숫자의 합이 입력 숫자 n과 같으면 결과를 출력하면 된다.만약 두 숫자의 합이 n보다 작으면 오른쪽으로 작은 값을 가리키는 변수를 이동한다.만약 두 숫자의 합이 n보다 크면, 비교적 큰 값을 가리키는 변수를 왼쪽으로 이동합니다.판단이 끝나는 조건은 두 변수가 중합되는 것이다.
다음은 이 해법의 코드입니다.
void find2(int *data,int num)
{
	assert(NULL!=data);

	int i=0;
	int j=len-1;
	while(i<j)
		{
			if((data[i]+data[j])==num)
				{
					printf(" %d + %d = %d  
",data[i],data[j],num);
					return;
				}
			else if((data[i]+data[j])< num)
				{
					i++;
				}
			else
				{
					j--;
				}
		}
	printf(" not find them  
");
	return;
}

소결


두 번째 해법의 시간 복잡도는 o(n)로 첫 번째 해법보다 우수하고 제목 중의 승차수조의 조건을 충분히 이용할 수 있음을 분명히 한다.
표시할 때 sourceType 전환
[Swift4] U I P op ver Presentation Controller를 사용하여 아이폰/iPad 두 가지를 지원하는 Popover를 출시했습니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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