我的思路是:
用队列,从(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=a[x]+b[y];
}
}
void main() {
for(int i=0;i<k*k;i++)
visited[i]=false;
queue.add(new Data(0, 0));
visited[0]=true;
result[count-1]=a[0]+b[0];
while(!queue.isEmpty())
{
Data data=queue.poll();
int t1=empty,t2=empty;//t1 t2初始为比最小还小的方便后面比较
if(data.value!=result[count-1])
{
result[count]=data.value;
if(++count==k)
break;
}
if(data.x+1<k && (!visited[(data.x+1)*k+data.y]))
{
t1=a[data.x+1]+b[data.y];
visited[(data.x+1)*k+data.y]=true;
}
if(data.y+1<k && (!visited[(data.x)*k+data.y+1]))
{
t2=a[data.x]+b[data.y+1];
visited[(data.x)*k+data.y+1]=true;
}
if((t1<t2&&t1!=empty) || (t1!=empty&&t2==empty) || (t1==t2 &&t1!=empty))
{
queue.add(new Data(data.x+1, data.y));
}
if((t1>t2&&t2!=empty) || (t2!=empty&&t1==empty) || (t1==t2 &&t2!=empty))
{
queue.add(new Data(data.x, data.y+1));
}
}
for(int i=0;i<count;i++)
{
System.out.print(result[i]+" ");
}
}
public static void main(String[] args)
{
new Test().main();
}
}
具体分析请见这个博文
http://blog.csdn.net/sunnianzhong/article/details/8932374
上面写道有三种方法,1:暴力 ,2:快排, 3:堆排
而我的方法,并没有排序,因为他本身有序,我只是根据规律通过队列入队出队来剪掉不必要的路径。因为没有大量的数据验证,可能会有错误。我用简单的数字举例是能通过的。
分享到:
相关推荐
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] ...
分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;
算法-数据结构- 树状数组.rar
代码实现://无论在总个数为奇数还是偶数k为其mid坐标,如果是偶数个K为后面的那个mid//将两个数组中相对小的那个数压入新数组思路:采用分治算法,将两个数组
算法-数据结构之【数组和广义表】复习题.rar
Giovanni Manzini and Paolo Ferragina 吸取了前人多种经验,结合n个算法,组建了最快的sa构建法.2005年新出的算法.是GNU开源项目,竞赛中 1000万的数据是 1 s,文件相当多,不能写在博客里,linux源码可以看: ...
学习笔记[韩顺平老师讲的数据结构和算法];数据结构和算法之稀疏数组。个人的一个理解。
给定一个整形数组和一个数字s,找到数组中最短的一个连续子数组,使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值public int minS
将两个有序数组,合并成另一个有序的数组,升序。将两个有序数组,合并成另一个有序的数组,升序。将两个有序数组,合并成另一个有序的数组,升序
分治算法求n个数的数组中找出第二个最大元素
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...
给定两个有序数组a b 使合并后的数组仍然有序 归并算法的事件复杂度为O logn
算法中数据结构的一个重要的应用,树状数组的两个应用。写的比较详尽
17082 两个有序数序列中找第k小(必做) 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: C++;C;VC;JAVA Description 已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为...
57春节7天练---Day-1:数组和链表 数组和链表.pdf
算法-数组排序 按数组内数字大小排序 取得最大值或最小值.rar
js代码-(算法)合并两个有序数组
算法设计与分析(王晓东版)2-11题:将数组的子数组a[0:k]和a[k+1:n-1]进行换位,要求最坏情况下时间复杂度为O(n)
python算法-数组和链表 数组和链表.pdf