Leetcode-Merge k Sorted Lists

---

昨天師兄的同事和他一起回實驗室看我們，順便交流了一下面試的事情。他在猿題庫碰到了面試題：merge K sorted arrays。我馬上就聯想到了Leetcode上的相似的題目，當時做的時候理解的不是很深，現在拿來再反思一下。

這道題目在分布式系統中非常常見，來自不同client的sorted list要在central server上面merge起來1。
有兩種方法：1.分治法；2.堆。

分治法

最初，我是逐個list合并，像滾雪球一樣，有序的list越來越長，直到與最后一個list合并后，所有的list合并成功。提交后超時。設每個list長度為n，由于merge的時間復雜度是O(n)，所有總的時間復雜度是：n(k?1)+n(k?2)+……+n=nk2。而這與插入排序法的時間復雜度一致。

所以，我們借用歸并排序的思想：將問題分解成兩個子任務，即分成前后各一半的list，分別將它們排成有序的list之后，再將兩個有序的list合并。這樣時間復雜度滿足:T(k)=T(k/2)+O(n?k)，T(k)=O(nklogk)。

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {if (NULL == l1)return l2;if (NULL == l2)return l1;struct ListNode *head = NULL;if (l1->val < l2->val){head = l1;head->next = mergeTwoLists(l1->next, l2);}else{head = l2;head->next = mergeTwoLists(l1, l2->next);}return head;}struct ListNode *mergeLists_sub(struct ListNode *lists[], int begin, int end) {if (begin > end)return NULL;if (begin == end)return lists[begin];int mid = (begin + end)/2;struct ListNode *left = mergeLists_sub(lists, begin, mid);struct ListNode *right = mergeLists_sub(lists, mid+1, end);return mergeTwoLists(left, right); }struct ListNode *mergeKLists(struct ListNode *lists[], int k) {return mergeLists_sub(lists, 0, k-1); }

堆（優先隊列）

基本思路是這樣的：
1.取每個list的第一個元素構成一個最小堆（或者說優先隊列），
2.重復以下步驟：
a.取出最小堆的第一個元素；（若用優先隊列，直接push()）
b.用a中取出的元素的所在list的下一個元素替換堆首元素，再重新使堆有序化。如果該list已經是空的話，就用無窮大代替。（若用優先隊列，先pop()，如果不為空，再push進a中取出的元素的所在list的下一個元素）
復雜度同分治法。

class nodeComparison {//此函數要加上public。//“>”說明是最小堆。“<”說明是最大堆 public: bool operator() (Node* n1, Node* n2){return n1->val > n2->val;} };Node* mergeKsortedLists(vector<Node*> &lists) {if (lists.empty())return NULL;priority_queue<Node*, vector<Node*>, nodeComparison> pq;int sz = lists.size();for (int i = 0; i < sz; i++){if (lists[i] != NULL)pq.push(lists[i]);}Node helper(0);Node *helper_ptr = &helper;while (!pq.empty()){Node *toAdd = pq.top();pq.pop();helper_ptr->next = toAdd;helper_ptr = toAdd;if (toAdd->next)pq.push(toAdd->next);}return helper.next; }

如果鏈表變成數組，該如何處理呢？這里的做法是把每個元素都變成一個struct node節點，存儲該元素所在二維數組的位置以及下一個元素，本質上和sorted lists一樣。但是如果是二維vector呢，每一維的長度可能不等，所以還得加上每個一維vector的長度。代碼寫得很精彩，正好可以復習一下今天寫的堆排序的相關代碼！！！

---

Merge k Sorted Lists http://www.tuicool.com/articles/ZnuEVfJ. ?

總結

以上是生活随笔為你收集整理的Leetcode-Merge k Sorted Lists的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。