Merge k Sorted Arrays (Ladder)

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   struct node {
    int val;
    int k;
    int pos;
    node(int _val, int _k, int _pos): val(_val), k(_k), pos(_pos) {}
    node(): val(0), k(0), pos(0) {}
   };
   struct comparator{
    bool operator() (struct node n1, struct node n2) {
        return n1.val > n2.val;
    }
   };
   class Solution {
   public:
    /**
     * @param arrays k sorted integer arrays
     * @return a sorted array
     */
    vector<int> mergekSortedArrays(vector<vector<int>>& arrays) {
        // Write your code here
        if (arrays.empty()) {
            return {};
        }
        const int k = arrays.size();
        bool notend = true;
        vector<int> result;
        priority_queue<node, vector<node>, comparator> minheap;
        int totalnum = 0;
        // put the front into minheap
        for (int i = 0; i < k; ++i) {
            if (arrays[i].empty()) {
                continue;
            }
            totalnum += arrays[i].size();
            int pos = 0;
            int val = arrays[i][pos]; 
            minheap.push(node(val, i, pos));
        }
        // find the min
        result.resize(totalnum);
        int index = 0;
        while (!minheap.empty()) {
            node tmp = minheap.top();
            minheap.pop();
            result[index++] = tmp.val;
            if (tmp.pos +1 < arrays[tmp.k].size()) {
                 tmp.pos += 1;
                 tmp.val = arrays[tmp.k][tmp.pos];
                minheap.push(tmp);
            }
        }
        return result;
    }
   };
   

Similar problems

x

Tags

x