[LintCode] 486 Merge k Sorted Arrays 解题报告

Description
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].



Challenge
Do it in O(N log k).

N is the total number of integers.
k is the number of arrays.



思路
先建立一个min-heap。
把每一个subarray的第一个数放进去。
当heap不空，每次拿出来一个最小的放进答案列表。
同时，把这个最小的数所在的subarray里的下一个数字放进去。
当heap里空了的时候，我们返回答案。



Code

class Record {
    int row;
    int col;
    int val;
    public Record(int row, int col, int val) {
        this.row = row;
        this.col = col;
        this.val = val;
    }
}

public class Solution {
    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    public List<Integer> mergekSortedArrays(int[][] arrays) {
        // Write your code here
        
        PriorityQueue<Record> heap = new PriorityQueue<Record>(arrays.length, new Comparator<Record>() {
            public int compare(Record x, Record y) {
                return x.val - y.val;
            }
        });
        
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i].length != 0) {
                heap.offer(new Record(i, 0, arrays[i][0]));
            }
        }
        
        List<Integer> result = new ArrayList<>();
        
        while (!heap.isEmpty()) {
            Record r = heap.poll();
            result.add(r.val);
            if (r.col + 1 < arrays[r.row].length) {
                heap.offer(new Record(r.row, r.col + 1, arrays[r.row][r.col + 1]));
            }
        }
        
        return result;
    }
}