假设有这么一道题
给定K个有序序列，输出合并后有序序列
A1=[5,8,11，。。。。]n
A2=[4,6,10，。。。。]n
A3=[1,2,3，。。。。]n
。。。。
AK=[100,200,300，。]n
这里n代表的是这个数组的长度是统一的。
在这里，我们给出三种做法
其算法复杂度不同
我们这里就先用
A1=[5,8,11]n
A2=[4,6,10]n
A3=[1,2,3]n
来做测试数据吧
方法一全部加起来再排序。时间复杂度O(nklog(nk))
A[]=A1[]+A2[]+…Ak[];
Sort(A[]);很蠢的一种方式
static void answer1(List<int[]> list)
{
int A[]=new int[(list.get(0)).length*list.size()];
for(int i=0,k=0;i<list.size();i++)
{
for(int j=0;j<list.get(0).length;j++,k++)
{
A[k]=list.get(i)[j];
}
}
System.out.println("方法一");
Arrays.sort(A);
for(int i=0;i<A.length;i++)
{
System.out.print(A[i]+" ");
}
System.out.println();
}
方法二 用类似于margsort的思想去求，时间复杂度O(nk^2)
static void answer2(List<int[]> list)
{
int A[]=new int[(list.get(0)).length*list.size()];
List<List<Integer>> curry=new ArrayList<List<Integer>>();
for(int i=0;i<list.size();i++)
{
List<Integer> temp=new ArrayList<Integer>();
for(int j=0;j<list.get(0).length;j++)
{
temp.add(list.get(i)[j]);
}
curry.add(temp);
}
int i=0,n=curry.size();
while(n!=0)
{
int min=curry.get(0).get(0),index=0;
for(int j=0;j<n;j++)
{
if(curry.get(j).get(0)<min)
{
min=curry.get(j).get(0);
index=j;
}
}
A[i]=min;
i++;
curry.get(index).remove(0);
List<List<Integer>> nullArr=new ArrayList<List<Integer>>();
List<Integer> nul=new ArrayList<Integer>();
nul.add(null);
nul.remove(null);
nullArr.add(nul);
curry.removeAll(nullArr);
n=curry.size();
}
System.out.println("方法二");
Arrays.sort(A);
for(int j=0;j<A.length;j++)
{
System.out.print(A[j]+" ");
}
System.out.println();
方法三 用堆去处理，时间复杂度是O(nklogk)
static void answer3(List<int[]> list)
{
PriorityQueue<Integer> temp=new PriorityQueue<Integer>();
for(int i=0;i<list.size();i++)
{
for(int j=0;j<list.get(i).length;j++)
{
temp.add(list.get(i)[j]);
}
}
System.out.println("方法三");
while(!temp.isEmpty())
{
System.out.print(temp.poll()+" ");
}
System.out.println();
}
很明显。最后一种方式最快。这也和堆的性质有关。堆比较适合用在那些需要多次取最值的问题中
