鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升

来源:互联网 作者:佚名 时间:2015-08-02 08:05
题目: 有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列,对于1=i,j=k,求k个最小的(aibj),要求算法尽量高效 . 解法: 本题可借助最小堆来解决,由于a1b1肯定是最小的和, 首先把 a1b1的结果放大最小堆里 ,此时堆中只有一个元素,自

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

解法:本题可借助最小堆来解决,由于a1+b1肯定是最小的和,首先把a1+b1的结果放大最小堆里,此时堆中只有一个元素,自然满足最小堆条件,然后开始出堆的操作,从堆里面取出根节点(也就是最小的值),假如此时堆顶元素为ai+bi,则需要像最小堆中压入a(i+1)+bj的和与ai+b(j+1)的和,当然,要保证下标不越界,如果下标越界了则忽略,另外要保证已经压入过堆中的组合(即使已经从堆中被取出了的)不再被压入堆中。不断地进行出堆、入堆的操作,重复k次,就得到了k个最小的组合值。

代码如下:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef struct sum_info
{
	int value;
	int i;
	int j;
}sum_info;
struct cmp
{
	bool operator()(sum_info a,sum_info b)
	{
		if(a.value>b.value)
			return true;
		else
			return false;
	}
};
int *min_k(int *A,int *B,int k);
int main()
{
	int k;
	cin>>k;
	int *A=new int[k];
	int *B=new int[k];
	int i;
	for(i=0;i<k;i++)
		cin>>A[i];
	for(i=0;i<k;i++)
		cin>>B[i];
	int *result=min_k(A,B,k);
	if(result!=NULL)
	{
		for(i=0;i<k;i++)
			cout<<result[i]<<" ";
		cout<<endl;
		delete []result;
	}
	delete []A;
	delete []B;
	return 0;
}
int *min_k(int *A,int *B,int k)
{
	if(A==NULL||B==NULL||k<=0)
		return NULL;
	priority_queue<sum_info,vector<sum_info>,cmp> q;//STL中的优先级队列是借助堆实现的,这里为了方便直接使用优先级队列
	sum_info tmp;
	tmp.value=A[0]+B[0];
	tmp.i=0;
	tmp.j=0;
	q.push(tmp);
	int *result=new int[k];
	int count,i,j;
	count=0;
	while(count<k)
	{
		tmp=q.top();
		result[count++]=tmp.value;
		i=tmp.i;
		j=tmp.j;
		q.pop();
		sum_info a,b;
		if((i+1)<k)
		{
			a.i=i+1;
			a.j=j;
			a.value=A[i+1]+B[j];
			q.push(a);
		}
		if((j+1)<k)
		{
			b.i=i;
			b.j=j+1;
			b.value=A[i]+B[j+1];
			q.push(b);
		}
	}
	return result;
}

由于堆的最大深度为logk,所以时间复杂度为klogk数量级,空间复杂度O(k).


网友评论
<