有两个序列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).