算法-求两个有序数组两两相加的值最小的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=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：堆排

而我的方法，并没有排序，由于他本身有序，我仅仅是依据规律通过队列入队出队来剪掉不必要的路径。由于没有大量的数据验证，可能会有错误。

我用简单的数字举例是能通过的。

算法-求两个有序数组两两相加的值最小的K个数的相关教程结束。