Problem

Given_k_sorted integer arrays, merge them into one sorted array.

Example

Given 3 sorted arrays:

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

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

思路一(heap)

• 因为每次合并都去取k个array中前面最小的值, 所以可以用heap来获得最小值
• 并且, 每次从heap中弹出值后, 都需要知道是从哪个array弹出来的, 并且这个值所在的位置, 这样我们能把它的下一个值放入heap中
• 直到heap为空即可

    public List<Integer> mergekSortedArrays(int[][] arrays) {
        List<Integer> res = new ArrayList<>();
        if (arrays == null || arrays.length == 0) {
            return res;
        }
        PriorityQueue<Point> heap = new PriorityQueue<>(1, new Comparator<Point>(){
            public int compare(Point p1, Point p2) {
                return p1.val - p2.val;
            }
        });
        int r = arrays.length;
        for (int i = 0; i < r; i++) {
            if (arrays[i] != null && arrays[i].length > 0)
                heap.add(new Point(i, 0, arrays[i][0]));
        }
        while (!heap.isEmpty()) {
            Point p = heap.poll();
            res.add(p.val);
            if (p.y + 1 < arrays[p.x].length) {
                heap.offer(new Point(p.x, p.y + 1, arrays[p.x][p.y + 1]));
            }
        }
        return res;
    }

    class Point {
        int x;
        int y;
        int val;
        public Point (int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }