LeetCode --- 23. Merge k Sorted Lists

タイトルリンク:Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
この問題の要件は,k個の秩序チェーンテーブルを1個の秩序チェーンテーブルに統合し,その複雑さを解析することである.
1.暴力合併
最も簡単な考え方は暴力合併であり、k個のチェーンテーブルを次々と合併することができる.たとえば、2番目から最後までを1番目のチェーンテーブルにマージします.時間的複雑さについては,各チェーンテーブル長がnであると仮定し,k個のチェーンテーブルがあるため,合計k−1回のマージが必要である.1回目の連結時の2つのチェーンテーブルの長さはいずれもnであり、時間複雑度はn+nであった.2回目の連結時の2つのチェーンテーブルの長さは2 nとnであり、時間的複雑度は2 n+nであった.このように,最後のマージ時の2つのチェーンテーブル長は(k−1)nとn,時間複雑度は(k−1)n+nであった.従って,全時間複雑度は2 n+3 n+...+kn = n(k*(k+1)/2 - 1) = O(nk2).
k個のチェーンテーブルから最小ノードを見つけるたびに、方法を採用することもできる.合計k*n個のノードが存在するため、最小ノードが見つかるたびに最悪の複雑度はkであるため、時間複雑度は同様にk*n*k=O(nk 2)である.
以上のように,複雑度が高く,タイムアウトしているので,ここではコードを付けない.
時間複雑度:O(nk 2)
空間複雑度:O(1)
2.ヒープ検索
上の暴力はk個のチェーンテーブルから最小ノードを見つける方法であり,スタックを用いて最小ノードを探すステップを最適化することができる.スタック削除および追加要素の複雑度はいずれもlogkであるため、時間的複雑度はk*n*logk=O(nklogk)に低下する.一方,空間複雑度はスタックを維持する必要があるためO(k)となる.
時間複雑度:O(nklogk)
空間複雑度:O(k)

 1 struct cmp
 2 {
 3     bool operator () (ListNode const *p1, ListNode const *p2)
 4     {
 5         return p1 -> val > p2 -> val;
 6     }
 7 };
 8 
 9 class Solution
10 {
11 public:
12     ListNode *mergeKLists(vector<ListNode *> &lists)
13     {
14         if(lists.size() == 0)
15             return NULL;
16         
17         priority_queue<ListNode *, vector<ListNode *>, cmp> q;
18         for(int i = 0; i < lists.size(); ++ i)
19             if(lists[i] != NULL)
20                 q.push(lists[i]);
21         
22         ListNode *h = new ListNode(0), *p = h;
23         while(!q.empty())
24         {
25             p -> next = q.top();
26             q.pop();
27             p = p -> next;
28             if(p -> next != NULL)
29                 q.push(p -> next);
30         }
31         return h -> next;
32     }
33 };

3.分治合併
これは集計ソートに似ており,分治法を用いてこの問題を解決している.チェーンテーブルを2つずつ結合することを考えているので,ここでは2つのチェーンテーブルを結合するアルゴリズムを用いる必要がある.処理するときは、再帰を選択したり反復を選択したりすることができます.の
連結中にチェーンテーブルの数が徐々に減少していることがわかります.k->k/2->k/4->…->2 -> 1.
同じように、チェーンテーブルの長さは徐々に正常になります.n->2 n->4 n->…->2^logk n.
従って、時間的複雑度は、k*n+k/2*2 n+k/4*4 n+...+1*2^logk n = nk + nk + nk + ... + nk = nklogk.空間の複雑さについては、もちろんO(1)ですね.
時間複雑度:O(nklogk)
空間複雑度:O(1)

 1 class Solution
 2 {
 3 public:
 4     ListNode *mergeKLists(vector<ListNode *> &lists) //       
 5     {
 6         if(lists.size() == 0)
 7             return NULL;
 8             
 9         if(lists.size() == 1)
10             return lists[0];
11         
12         for(int i = 0, l = lists.size(); i < l / 2; ++ i)
13         {
14             lists[i] = mergeTwoLists(lists[i], lists[lists.size() - 1]);
15             lists.pop_back();
16         }
17         
18         return mergeKLists(lists);
19     }
20     /*******************************  *******************************/
21     ListNode *mergeKLists(vector<ListNode *> &lists) //       
22     {
23         if(lists.size() == 0)
24             return NULL;
25         
26         int r = lists.size() - 1;
27         while(r > 0)
28             for(int l = 0; l < r; ++ l, --r)
29                 lists[l] = mergeTwoLists(lists[l], lists[r]);
30         
31         return lists[0];
32     }
33 private:
34     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
35     {
36         ListNode *h = new ListNode(0), *p = h;
37         
38         while(l1 != NULL && l2 != NULL)
39         {
40             if(l1 -> val < l2 -> val)
41             {
42                 p -> next = l1;
43                 l1 = l1 -> next;
44             }
45             else
46             {
47                 p -> next = l2;
48                 l2 = l2 -> next;
49             }
50             
51             p = p -> next;
52         }
53         
54         if(l1 != NULL)
55             p -> next = l1;
56         else
57             p -> next = l2;
58         
59         return h -> next;
60     }
61 };

転載は出典:LeetCode---23.Merge k Sorted Lists