알고리즘 서론 2.3 - 7 (정렬 되 지 않 은 배열) 과 검 지 offer 면접 문제 41 (정렬 배열)
알고리즘 서론 의 문제 풀이 방향: 모두 배열 에 먼저 병합 순 서 를 하고 시간 복잡 도 는 O (nlgn) 이 며 후속 방법 은 두 문제 가 일치 합 니 다.
방법 1: 1. 두 개의 지침 을 각각 배열 의 머리 와 꼬리 2, 계산 과 2.1 을 가리 키 며 목표 보다 크 면 꼬리 지침 은 앞으로 이동 합 니 다. 2.2 목표 보다 작 으 면 머리 지침 은 뒤로 이동 합 니 다.
bool FindNumberWithSum(int *data,int length,int sum,int *num1,int *num2)
{
if(data==nullptr || length<=0 || num1==nullptr || num2==nullptr)
return false;
bool isfound = false;
int fount = 0,tail = length -1;
while(fount < tail)
{
if(data[fount] + data[tail]== sum)
{
isfound = true;
*num1 = data[fount];
*num2 = data[tail];
break;
}
else if(data[fount] + data[tail] > sum)
tail--;
else
fount++;
}
return isfound;
} 코드 에 while 순환 이 양 끝 에서 중간 으로 배열 을 스 캔 하기 때문에 알고리즘 의 시간 복잡 도 O (n)
방법 2: 이분 검색 법 으로 y, y = x - a [i] 를 찾 습 니 다. 알고리즘 의 시간 복잡 도 는 nlogn 보다 작 기 때문에 전체적인 시간 복잡 도 는 nlogn 입 니 다.
//
bool binary_search(int a[],int v,int begin,int end)
{
int left=begin,right=end;
int mid=0;
while(left<=right){
mid=(left+right)/2;
if(a[mid]==v)
return True;
else if(a[mid]<v)
left=mid+1;
else
right=mid-1;
}
return false;
}
// a ， x
bool check_sum(int a[],int n,int x)
{
sort(a);// O(nlgn) a ， 《 》
for(int i=0;i<n;++i)
if(binary_search(a,x-a[i],0,n-1))
return true;
return false;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 프로그래머 면접에서의 다중 스레드 문제 요약wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
