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