首页 > 代码库 > 算法-求两个有序数组两两相加的值最小的K个数
算法-求两个有序数组两两相加的值最小的K个数
我的思路是:
用队列, 从(0,0)开始入队,每次出队的时候,选(1,0) (0,1) 之间最小的入队,如果是相等的都入队,如果入过队的就不入了,把出队的k个不同的输出来即可
我测试了几组数据都是对的,但是可能还是会有BUG,或者我忽略的地方。下面是我的实现代码(如果有错,请大家积极指正)
import java.util.LinkedList; import java.util.Queue; /** * 有两个序列 A 和 B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A 和 B 都按升序排列,对于 1<=i,j<=k,求 k 个最小的(ai+bj),要求算法尽量高效 * @author Administrator * */ public class Test { int k=4; int a[]=new int[]{1,2,3,4}; int b[]=new int[]{20,30,40,50}; boolean visited[]=new boolean[k*k]; int count=1,empty=a[0]+b[0]-1; Queue<Data> queue=new LinkedList<Data>(); int result[]=new int[k]; class Data{ public int x,y,value; public Data(int x,int y) { this.x=x; this.y=y; this.value=http://www.mamicode.com/a[x]+b[y];>
具体分析请见这个博文http://blog.csdn.net/sunnianzhong/article/details/8932374
上面写道有三种方法,1:暴力 ,2:快排, 3:堆排
而我的方法,并没有排序,因为他本身有序,我只是根据规律通过队列入队出队来剪掉不必要的路径。因为没有大量的数据验证,可能会有错误。我用简单的数字举例是能通过的。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。