|
题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。 分析：1.直接穷举。从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此方法与数组有序或者无序无关，时间复杂度为O(n)。 
 1 #include <iostream.h> 2 3 bool Find2Num(int *data,int n,int sum,int &num1,int &num2) 4 { 5 if (NULL==data || n<=1) 6 { 7 return false; 8 } 9 10 for (int i=0;i<n;i++) 11 { 12 for (int j=i+1;j<n;j++) 13 { 14 if (data[i]+data[j]==sum) 15 { 16 num1=data[i]; 17 num2=data[j]; 18 return true; 19 } 20 else 21 { 22 continue; 23 } 24 } 25 } 26 27 return false; 28 } 29 30 void main() 31 { 32 int data[6]={1,2,4,7,15,11}; 33 int sum=15; 34 int num1,num2; 35 36 if (Find2Num(data,6,sum,num1,num2)) 37 { 38 cout<<num1<<" "<<num2<<endl; 39 } 40 else 41 { 42 cout<<"doesn't exsit!"<<endl; 43 } 44 45 } 2.对每个a[i],然后查找sum-a[i]是否也在原始序列中，在查找的过程中采用二分查找，然而二分查找需序列是有序的，所以需要对数组进行排序。排序所需的时间为O(N*logN)。对N个a[i]，每个都需要花费O(logN)的时间去查找，故查找的过程所需时间为O(N*logN).总的花费时间为O(N*logN+N*logN)=O(N*logN)。
1 #include <iostream.h> 2 #include <algorithm> 3 using namespace std; 4 5 int BinarySearch(int *data,int n,int num) 6 { 7 int low=0; 8 int high=n-1; 9 int middle,position; 10 while(low<=high) 11 { 12 middle=(low+high)/2; 13 if (data[middle]<num) 14 { 15 low=middle+1; 16 } 17 else if (data[middle]>num) 18 { 19 high=middle-1; 20 } 21 else 22 { 23 position=middle; 24 25 return position; 26 } 27 } 28 29 30 return -1; 31 } 32 33 bool FindSum2(int *data,int n,int sum,int &num1,int &num2) 34 { 35 if (NULL==data || n<=1) 36 { 37 return false; 38 } 39 40 int findnum,index; 41 42 for (int i=0;i<n;i++) 43 { 44 findnum=sum-data[i]; 45 index=BinarySearch(data,n,findnum); 46 if (index!=-1 && index!=i) 47 { 48 num1=data[i]; 49 num2=data[index]; 50 return true; 51 } 52 else 53 { 54 continue; 55 } 56 } 57 58 return false; 59 60 } 61 62 void main() 63 { 64 int data[6]={1,2,4,7,15,11}; 65 int sum=15; 66 int num1,num2; 67 sort(data,data+6); 68 69 if (FindSum2(data,6,sum,num1,num2)) 70 { 71 cout<<num1<<" "<<num2<<endl; 72 } 73 else 74 { 75 cout<<"doesn't exsit!"<<endl; 76 } 77 78 } 3.如果数组是无序的，则首先采用快速排序算法排好序，所需时间为O(N*logN)。然后用两个指针i,j，分别指向数组的首端和尾端，令i=0,j=n-1；然后i++,j--;逐次判断a[i]+a[j]？=sum。如果某时刻a[i]+a[j]>sum，则j--，i不动;如果某时刻a[i]+a[j]<sum,则i++，j不动。终止条件是i>=j。此遍历过程的时间复杂度为O(N),所以此方法总的时间复杂度为O(N*logN+N)=O(N*logN).倘若数组本身是有序的，则此方法的时间复杂度降为O(N)。
1 #include <iostream.h> 2 #include <algorithm> 3 using namespace std; 4 5 bool Find2Num(int *data,int n,int sum,int &num1,int &num2) 6 { 7 if (NULL==data || n<=1) 8 { 9 return false; 10 } 11 12 int *begin=data; 13 int *last=data+n; 14 sort(begin,last);//排序 15 16 int low=0,high=n-1; 17 while(low<high) 18 { 19 if (data[low]+data[high]<sum) 20 { 21 low++; 22 } 23 else if (data[low]+data[high]>sum) 24 { 25 high--; 26 } 27 else 28 { 29 num1=data[low]; 30 num2=data[high]; 31 return true; 32 } 33 } 34 35 return false; 36 37 } 38 39 void main() 40 { 41 int data[6]={1,2,4,7,15,11}; 42 int num1,num2; 43 int sum=15; 44 bool flag=Find2Num(data,6,sum,num1,num2); 45 if (flag) 46 { 47 cout<<"exist two numers:"<<num1<<" and "<<num2<<" which theirs sum equal to "<<sum<<endl; 48 } 49 else 50 { 51 cout<<"doesn't exist!"<<endl; 52 } 53 }
 1 #include <iostream.h> 2 #include <algorithm> 3 #include <utility> 4 using namespace std; 5 6 7 pair<int,int> FindSum(int *data,int n,int sum) 8 { 9 if (NULL==data || n<=1) 10 { 11 return make_pair(-1,-1); 12 } 13 14 sort(data,data+n);//排序 15 16 int *begin=data; 17 int *last=data+n-1; 18 19 while(begin<last) 20 { 21 if (*begin+*last<sum) 22 { 23 begin++; 24 } 25 else if (*begin+*last>sum) 26 { 27 last--; 28 } 29 else 30 { 31 return make_pair(*begin,*last); 32 } 33 } 34 35 return make_pair(-2,-2); 36 } 37 38 void main() 39 { 40 int data[6]={1,2,4,7,15,11}; 41 int sum=15; 42 pair<int,int> p; 43 p=FindSum(data,6,sum); 44 cout<<p.first<<" "<<p.second<<endl; 45 } |
|
|
