Merge k Sorted Arrays

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

http://www.lintcode.com/en/problem/merge-k-sorted-arrays/

Discussion

思想完全类似Merge K sorted list的思想，只是要考虑如何根据当前结点找到下一个节点，这在list里不是问题。

Solution

//O(nlogk) rum time //O(k) space

class Node {
public: 
    int row;
    int col;
    int val;
    Node (int i, int j, int v) : row(i), col(j), val(v) {};
};
struct mycom {
bool operator() (Node &A, Node &B) {
    return A.val > B.val;
}
};

class Solution {
public:
    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    vector<int> mergekSortedArrays(vector<vector<int>>& arrays) {
        vector<int> result;
        if(arrays.empty()) return result;
        priority_queue<Node, vector<Node>, mycom > myque;
        //create a heap
        for(int i=0; i<arrays.size(); i++) {
            if(arrays[i].empty() == false)
                myque.emplace(Node(i, 0, arrays[i][0]));
        }
        //maintain this heap, out the smallest one by one
        while(myque.empty() == false) {
            Node curnode = myque.top();
            result.emplace_back(curnode.val);
            myque.pop();
            //what's the next element??? So I need this info: the top element is from which vector?
            //pseudo code: myque.emplace(arrays[idx].next);
            if(curnode.col + 1 < arrays[curnode.row].size())
                myque.emplace(Node(curnode.row, curnode.col+1, arrays[curnode.row][curnode.col+1]));
        }
    }
};

除了自定义comparison structure，还可以重载小于操作符

class Node {
public: 
    int row;
    int col;
    int val;
    Node (int i, int j, int v) : row(i), col(j), val(v) {};
    bool operator < (const Node &B) const {
        return val > B.val;
    }
};

class Solution {
public:
    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    vector<int> mergekSortedArrays(vector<vector<int>>& arrays) {
        vector<int> result;
        if(arrays.empty()) return result;
        //priority_queue<Node, vector<Node>, mycom > myque;
        priority_queue<Node> myque;
        //create a heap
        for(int i=0; i<arrays.size(); i++) {
            if(arrays[i].empty() == false)
                myque.emplace(Node(i, 0, arrays[i][0]));
        }
        //maintain this heap, out the smallest one by one
        while(myque.empty() == false) {
            Node curnode = myque.top();
            result.emplace_back(curnode.val);
            myque.pop();
            //what's the next element??? So I need this info: the top element is from which vector?
            //pseudo code: myque.emplace(arrays[idx].next);
            if(curnode.col + 1 < arrays[curnode.row].size())
                myque.emplace(Node(curnode.row, curnode.col+1, arrays[curnode.row][curnode.col+1]));
        }
    }
};