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

题目：有两个序列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

#include  
using namespace std;  
int *min_k(int *A,int *B,int len1,int len2,int k);  
int main()  
{  
    int len1,len2,k;  
    cin>>len1>>len2>>k;//输入两个数组的长度len1,len2以及最小的和的数目  
    int *A=new int[len1];  
    int *B=new int[len2];  
    int i;  
    for(i=0;i>A[i];  
    for(i=0;i>B[i];  
    int *result=min_k(A,B,len1,len2,k);  
    for(i=0;i0&&j>0)  
    {  
        if(A[i-1]>B[j-1])  
        {  
            if((i-1)*j>=k)  
                i--;  
            else   
                break;  
        }  
        else  
        {  
            if((j-1)*i>=k)  
                j--;  
            else   
                break;  
        }  
    }  
    int count=0;  
    if(A[i-1]>B[j-1])  
    {  
        int p,q;  
        for(p=0;p

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