Merge K Sorted Arrays

• Lintcode : 486 / Leetcode 23(Similar)
• Level : Medium

Problem

Given k sorted integer arrays, merge them into one sorted array.

Example
Example 1:

Input: 
  [
    [1, 3, 5, 7],
    [2, 4, 6],
    [0, 8, 9, 10, 11]
  ]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Example 2:

Input:
  [
    [1,2,3],
    [1,2]
  ]
Output: [1,1,2,2,3]
Challenge
Do it in O(N log k).

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

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(nlogm) (m rows, n columns)
space: O(n * m)

Answer

class Node {
public:
    int r, c, val;
    Node (int _r, int _c, int _val) : r(_r), c(_c), val(_val) {}
};
struct cmp {
    bool operator() (const Node &a, const Node &b) {
        return a.val > b.val;
    }
};
class Solution {
public:
    vector<int> mergekSortedArrays(vector<vector<int>> &arrays) {
        priority_queue<Node, vector<Node>, cmp> pq;
        for (int i = 0; i < arrays.size(); i++) {
            if (arrays[i].empty()) continue;
            pq.push(Node(i, 0, arrays[i][0]));
        }
        vector<int> ans;
        while (!pq.empty()) {
            Node n = pq.top(); pq.pop();
            ans.push_back(n.val);
            if (n.c + 1 < arrays[n.r].size()) pq.push(Node(n.r, n.c + 1, arrays[n.r][n.c + 1]));
        }
        return ans;
    }
};

tags: heap

​