2015年9月28日星期一

Lintcode: Merge k sorted lists


Codes and Thoughts reference:
http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html

Priority queue solution:

Introduction to data structure of priority_queue:
http://m.zgxue.com/197/1977189.html

Great Explanation of how to rewrite compare function of priority_queue
http://www.cnblogs.com/iammatthew/archive/2010/08/19/1803935.html

C++ operator overloading
http://c.biancheng.net/cpp/biancheng/view/215.html

Time: O(nk*logk)
Space: O(k)

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};



Merge two lists -- basic solution
n -- the maximum len of each list  k -- the number of sorted lists
for merge two list O(m+n)   ==> Portal to my leetcode Merge two sorted lists solution
here: n + 2n + 3n + ... + kn =((k+1)*k/2 - 1)*n

Time: O(nk^2)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *res = NULL;
        for(int i = 0; i < lists.size(); i++){
            res = merge(res, lists[i]);
        }
        return res;
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

Bisection:
//thoughts
http://www.cnblogs.com/TenosDoIt/p/3673188.html

Time: O(nk*logk)    ---- each level is O(nk) and there are logk levels
Space: O(1)

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int end = lists.size() - 1;
        while(end){
            int begin = 0;
            while(begin < end){
                lists[begin] = merge(lists[begin], lists[end]);
                begin++;
                end--;
            }
        }
        return lists[0];
    }
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};



发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)