Merge k Sorted Arrays 486

Question

将 k 个排序数组合并为一个大的排序数组。

Example

给出下面的 3 个排序数组:

[ [1, 3, 5, 7],

[2, 4, 6],

[0, 8, 9, 10, 11] ]

合并后的大数组应为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Solution

与Merge K sorted Lists一样，用PriorityQueue(Heap)实现。也可以用D&C。

代码如下：

public class test {
    public static void main(String[] args){
        ArrayList<Integer> a = new ArrayList<Integer>();
        a.add(1);
        a.add(3);
        a.add(5);
        ArrayList<Integer> b = new ArrayList<Integer>();
        b.add(2);
        b.add(4);
        ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>();
        array.add(a);
        array.add(b);
        test t = new test();
        ArrayList<Integer> result = t.mergeKArray(array);
        for(int i : result){
            System.out.println(i);
        }
    }

    public ArrayList<Integer> mergeKArray(ArrayList<ArrayList<Integer>> arrays){
        ArrayList<Integer> merge = new ArrayList<Integer>();
        for(ArrayList<Integer> array : arrays){
            for(int i : array){
                merge.add(i);
            }
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(merge);

        ArrayList<Integer> res = new ArrayList<Integer>();

        while(!queue.isEmpty()){
            res.add(queue.poll());
        }

        return res;
    }
}

Related Question

之后补上