有两个序列A跟B,A=(a1,a2,ak),B=(b1,b2,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算

有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算法尽量高效 .

题目：有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算法尽量高效 .

解法：设定两个下标i，j分别指向A,B的尾部，若当前（i-1）*j>=k或(j-1)*i>=k说明，剩下的组合是最小的i*j，而且可以根据A[i]，B[j]两个元素的大小分别移动相应的下标，直到（i-1）*j<k或(j-1)*i<k，此时剩下的组合数为i*j，遍历数组求得前k个最小和，返回给用户。

[cpp] view plaincopy

1. #include<iostream>  
2. using namespace std;  
3. int *min_k(int *A,int *B,int len1,int len2,int k);  
4. int main()  
5. {  
6.     int len1,len2,k;  
7.     cin>>len1>>len2>>k;//输入两个数组的长度len1,len2以及最小的和的数目  
8.     int *A=new int[len1];  
9.     int *B=new int[len2];  
10.     int i;  
11.     for(i=0;i<len1;i++)  
12.         cin>>A[i];  
13.     for(i=0;i<len2;i++)  
14.         cin>>B[i];  
15.     int *result=min_k(A,B,len1,len2,k);  
16.     for(i=0;i<k;i++)  
17.         cout<<result[i]<<" ";  
18.     cout<<endl;  
19.     delete []A;  
20.     delete []B;  
21.     delete []result;  
22.     return 0;  
23. }  
24. int *min_k(int *A,int *B,int len1,int len2,int k)  
25. {  
26.     if(A==NULL||B==NULL||k<=0)  
27.         return NULL;  
28.     int i,j;  
29.     int *tmp=new int[k];  
30.     i=len1;  
31.     j=len2;  
32.     while(i>0&&j>0)  
33.     {  
34.         if(A[i-1]>B[j-1])  
35.         {  
36.             if((i-1)*j>=k)  
37.                 i--;  
38.             else   
39.                 break;  
40.         }  
41.         else  
42.         {  
43.             if((j-1)*i>=k)  
44.                 j--;  
45.             else   
46.                 break;  
47.         }  
48.     }  
49.     int count=0;  
50.     if(A[i-1]>B[j-1])  
51.     {  
52.         int p,q;  
53.         for(p=0;p<i;p++)  
54.         {  
55.             for(q=0;q<j;q++)  
56.             {  
57.                 if(count<k)  
58.                     tmp[count++]=A[p]+B[q];  
59.                 else  
60.                     break;  
61.             }  
62.         }  
63.     }  
64.     else  
65.     {  
66.         int p,q;  
67.         for(p=0;p<j;p++)  
68.         {  
69.             for(q=0;q<i;q++)  
70.             {  
71.                 if(count<k)  
72.                     tmp[count++]=B[p]+A[q];  
73.                 else  
74.                     break;  
75.             }  
76.         }  
77.     }  
78.     return tmp;  
79. }  

时间复杂度为min{O(min(len1,len2))，O(k)}，空间复杂度为O(k)，若只是需要输出最小的k个和，则不需要用O(k)的空间把k个最小和存储起来，这样时间复杂度为O(1).

查看更多 下一篇