//Merge K sorted arrays(length:n). O(n*k*logk).
class Solution{
private:
struct cmp{
bool operator()(heapNode l, heapNode r){
if(l.val < r.val) return false;
else return true;
}
};
typedef struct _heapNode{
int val;
int i; //
int j; //
}heapNode;
//priority_queue<heapNode, vector<heapNode>, cmp> h; //Min heap.
public:
vector<int> mergeKsortedArray(vector<vector<int>> &karray){
int k= karray.size();
int n= karray[0].size();
vector<int> res;
priority_queue<heapNode, vector<heapNode>, cmp> h; //Min heap.
//Initialize k heapNode, store the first element.
struct heapNode[k] harr;
for(int i=0;i<k;++i){
harr[i].val = karray[i][0];
harr[i].i = i; // index of which array.
harr[i].j = 0; // Index of element to be stored from array i.
h.push(harr[i]);
}
while(!h.empty()){
heapNode minpop = h.top();
h.pop();
int i = minpop.i; //To indicate the index of array.
int j = minpop.j;
if(j < n-1){
harr[i].j = j+1;
harr[i].val = karray[i][j+1]; //To push the next ele int the array into heap.
h.push(harr[i]);
}
res.push_back(minpop.val);
}
return res;
}
};
//Merge K sorted lists. O(n*k*logk).
class Solution {
private:
struct cmp{
bool operator()(ListNode* lhs, ListNode *rhs){
if(lhs->val < rhs->val) return false;
else return true;
}
};
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
int K = lists.size();
if (K == 0) return NULL;
else if (K == 1) return lists[0];
ListNode *listHead(NULL), *listRear(NULL);
ListNode *node(NULL);
priority_queue<ListNode*, vector<ListNode*>, cmp> h;
// push K list heads into heap
for(int i=0; i<K; ++i)
if(lists[i] != NULL){
h.push(lists[i]);
lists[i] = lists[i]->next;
}
while(!h.empty()){
//pop the min of k nodes in the heap.
node = h.top();
h.pop();
if(node->next){
h.push(node->next); //***,pop one ele, push the next ele in the same list into heap.
}
//insert into mergerd new list.
if(!listHead){
listHead = listRear = node;
}else{
listRear->next = node;
listRear = node;
}
}
return listHead;
}
};
No comments:
Post a Comment