Tuesday, June 17, 2014

Merge K sorted arrays -- Leetcode

//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