文章目錄
- 題目描述
- 知識點
- 結果
- 碼前思考
- 代碼實作
- 碼後反思
- 參考文檔
- 二刷代碼
題目描述
知識點
連結清單，分治，堆（優先隊列）
結果
碼前思考
- 這道題是LeetCode 21. Merge Two Sorted Lists的更新版，我們在LeetCode 21. Merge Two Sorted Lists中講過可以使用prev或者是遞歸來優化我之前的代碼；
- 我采用的是逐個合并的寫法，屬于不用動腦子的暴力寫法！正确的寫法應該是分治（見碼後放思）
代碼實作
//我不知道這道題賣的是什麼藥，感覺就是很普通的連結清單合并操作，還有那個堆，是認真的嗎？
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int size = lists.size();
if(size == 0){
return NULL;
}
if(size == 1){
return lists[0];
}
ListNode* dummyHead = new ListNode(0);
//先将第一個連結清單加入到dummyNode裡
dummyHead->next = lists[0];
int cnt = 1;
for(;cnt<size;cnt++){
//記錄前驅是哪個
ListNode* prev = dummyHead;
//連結清單1的指針
ListNode* l1 = dummyHead->next;
//連結清單2的指針
ListNode* l2 = lists[cnt];
while(l1 != NULL && l2 != NULL){
//開始進行合并
if(l1->val >= l2->val){
prev->next = l2;
prev = l2;
l2 = l2->next;
}else{
prev->next = l1;
prev = l1;
l1 = l1->next;
}
}
if(l1!=NULL){
prev->next = l1;
}
if(l2!=NULL){
prev->next = l2;
}
}
return dummyHead->next;
}
};
碼後反思
-
我上面是暴力求解，這個題目實際想考察的是分治（類似于歸并排序）的思想，使用了兩重遞歸，一次是分治的遞歸；一次是合并兩個連結清單的遞歸（當然，這個遞歸也可以改成疊代）。
結果如下：
代碼如下： LeetCode 23. Merge k Sorted Lists【有序連結清單合并+模拟歸并排序】⭐⭐⭐⭐⭐題目描述知識點結果參考文檔二刷代碼 //使用歸并排序的思想——分支進行解題 //對于一個大問題，我們不好求解，那麼我們就從小的方面進行求解 //将大問題進行細分 //這就是手寫歸并排序呀，唉，我太菜了，歸并排序的時間複雜度原理還沒有了解清楚 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size() == 0){ return NULL; } return mergeSort(lists,0,lists.size()-1);; } //遞歸函數的意思是傳回以start和end之間的有序連結清單的頭節點 ListNode* mergeSort(vector<ListNode*>& lists,int start,int end){ //兩者相等時，說明隻有一個連結清單了，不能再進行細分了，直接傳回結果 if(start == end){ return lists[start]; }else{ //如果還可以再進行細分 int mid = (start+end) / 2; ListNode* l1 = mergeSort(lists,start,mid); ListNode* l2 = mergeSort(lists,mid+1,end); //合并兩個連結清單 return merge(l1,l2); } } //采用遞歸的方式來合并兩個連結清單 ListNode* merge(ListNode* l1,ListNode* l2){ //遞歸的邊界，先空着 if(l1 == NULL){ //l1等于NULL，說明剩下的都是l2，兩者不可能同時為NULL！ return l2; } if(l2 == NULL){ //l2等于NULL，說明剩下的全是l1 return l1; } if(l1->val >= l2->val){ //說明l2這個值在前面 l2->next = merge(l1,l2->next); return l2; }else{ l1->next = merge(l1->next,l2); return l1; } } }; -
分治算法和逐個合并的時間複雜度的差別：
兩個連結清單聚合确實發生了K-1次。但是注意，題解中把 K個連結清單兩兩聚合，生成K/2個連結清單的過程叫一次Merging。然後這樣的Merging總共發生log(K)次。每一次Merging需要比較的次數是N。 是以總的時間複雜度是O(N*log(K))。這才是兩兩聚合和逐一聚合的本質差别。 逐一聚合的情況下，兩個聚合的連結清單長度會發生偏斜，其中一個連結清單長度越來越長。考慮 最壞情況K個連結清單（極端情況） 每個僅包含一個元素（N為總元素數，這裡N=K)，那麼逐一聚合的總複雜度就是O(1+2+3+…N-1) = O(K*N). 而兩兩聚合的情況下，仍然考慮剛才的例子，
第一輪K個連結清單，聚合完成後剩K/2個，發生的比較次數是 1 + 1 + 1 + …+ 1 =1*K = N.
第二輪K/2個連結清單，聚合完成後剩K/4個，發生的比較次數是(最壞情況) 2+2+2+ … + 2 = 2 * K/2 = N .
第三輪K/4個連結清單，聚合完成後剩K/8個，發生的比較次數 4 + 4 + 4 + … + 4 = 4 * K/4 = N .
…
最後一輪剩2個連結清單，比較次數 K/2 + K/2 = 2* K/2 = N .
總共有log(K)輪，總比較次數 N*log(K)
- 至于使用優先隊列的方法我就沒考慮了，以後再寫。
參考文檔
- C++ 優先隊列&兩兩合并&分治合并（圖解）
- 合并K個排序連結清單
二刷代碼
知道不能直接使用暴力了，同時也知道使用 N l o g k Nlogk Nlogk的方法解題。
但是我使用的是疊代的寫法，而不是遞歸的寫法：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//暴力一個一個周遊肯定會逾時，類似于歸并排序！減少周遊的次數？也就是折半一下
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int len = lists.size();
if(len==0){
return NULL;
}
while(lists.size()!=1){
vector<ListNode*> tmp;
//兩兩合并
for(int i=0;i<lists.size();i=i+2){
if(i+1<lists.size()){
tmp.push_back(merge(lists[i],lists[i+1]));
}else{
tmp.push_back(lists[i]);
}
}
lists=tmp;
}
return lists[0];
}
ListNode* merge(ListNode* l1,ListNode* l2){
ListNode* dummyNode = new ListNode(0);
ListNode* prev = dummyNode;
while(l1!=NULL && l2!=NULL){
if(l1->val < l2->val){
prev->next = l1;
prev = l1;
l1=l1->next;
}else{
prev->next = l2;
prev = l2;
l2=l2->next;
}
}
if(l1!=NULL){
prev->next=l1;
}
if(l2!=NULL){
prev->next=l2;
}
return dummyNode->next;
}
};