??????????????? 原題鏈接:?http://oj./problems/merge-k-sorted-lists/?
這道題目在分布式系統(tǒng)中非常常見(jiàn)，來(lái)自不同client的sorted list要在central server上面merge起來(lái)。這個(gè)題目一般有兩種做法，下面一一介紹并且分析復(fù)雜度。 第一種做法比較容易想到，就是有點(diǎn)類似于MergeSort的思路,就是分治法，不了解MergeSort的朋友，請(qǐng)參見(jiàn)歸并排序-維基百科，是一個(gè)比較經(jīng)典的O(nlogn)的排序算法，還是比較重要的。思路是先分成兩個(gè)子任務(wù)，然后遞歸求子任務(wù)，最后回溯回來(lái)。這個(gè)題目也是這樣，先把k個(gè)list分成兩半，然后繼續(xù)劃分，知道剩下兩個(gè)list就合并起來(lái)，合并時(shí)會(huì)用到Merge?Two Sorted Lists這道題，不熟悉的朋友可以復(fù)習(xí)一下。代碼如下：? public ListNode mergeKLists(ArrayList<ListNode> lists) {??? if(lists==null || lists.size()==0)??????? return null;??? return helper(lists,0,lists.size()-1);}private ListNode helper(ArrayList<ListNode> lists, int l, int r){??? if(l<r)??? {??????? int m = (l r)/2;??????? return merge(helper(lists,l,m),helper(lists,m 1,r));??? }??? return lists.get(l);}private ListNode merge(ListNode l1, ListNode l2){ ??? ListNode dummy = new ListNode(0);??? dummy.next = l1;??? ListNode cur = dummy;??? while(l1!=null && l2!=null)??? {??????? if(l1.val<l2.val)??????? {??????????? l1 = l1.next;??????? }??????? else??????? {??????????? ListNode next = l2.next;??????????? cur.next = l2;??????????? l2.next = l1;??????????? l2 = next;??????? }??????? cur = cur.next;??? }??? if(l2!=null)??????? cur.next = l2;??? return dummy.next;}
我們來(lái)分析一下上述算法的時(shí)間復(fù)雜度。假設(shè)總共有k個(gè)list，每個(gè)list的最大長(zhǎng)度是n，那么運(yùn)行時(shí)間滿足遞推式T(k) = 2T(k/2) O(n*k)。根據(jù)主定理，可以算出算法的總復(fù)雜度是O(nklogk)。如果不了解主定理的朋友，可以參見(jiàn)主定理-維基百科。空間復(fù)雜度的話是遞歸棧的大小O(logk)。
接下來(lái)我們來(lái)看第二種方法。這種方法用到了堆的數(shù)據(jù)結(jié)構(gòu)，思路比較難想到，但是其實(shí)原理比較簡(jiǎn)單。維護(hù)一個(gè)大小為k的堆，每次取堆頂?shù)淖钚≡胤诺浇Y(jié)果中，然后讀取該元素的下一個(gè)元素放入堆中，重新維護(hù)好。因?yàn)槊總€(gè)鏈表是有序的，每次又是去當(dāng)前k個(gè)元素中最小的，所以當(dāng)所有鏈表都讀完時(shí)結(jié)束，這個(gè)時(shí)候所有元素按從小到大放在結(jié)果鏈表中。這個(gè)算法每個(gè)元素要讀取一次，即是k*n次，然后每次讀取元素要把新元素插入堆中要logk的復(fù)雜度，所以總時(shí)間復(fù)雜度是O(nklogk)?？臻g復(fù)雜度是堆的大小，即為O(k)。代碼如下：
public ListNode mergeKLists(ArrayList<ListNode> lists) {??? PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){??????????? @Override??????????? public int compare(ListNode n1, ListNode n2)??????????? {??????????????? return n1.val-n2.val;??????????? }??????? });??? for(int i=0;i<lists.size();i )??? {??????? ListNode node = lists.get(i); ??????? if(node!=null)??????? {??????????? heap.offer(node);??????? }??? }??? ListNode head = null;??? ListNode pre = head;??? while(heap.size()>0)??? {??????? ListNode cur = heap.poll();??????? if(head == null)??????? {??????????? head = cur;??????????? pre = head;??????? }??????? else??????? {??????????? pre.next = cur;??????? }??????? pre = cur;??????? if(cur.next!=null)??????????? heap.offer(cur.next);??? }??? return head;}
可以看出兩種方法有著同樣的時(shí)間復(fù)雜度，都是可以接受的解法，但是卻代表了兩種不同的思路，數(shù)據(jù)結(jié)構(gòu)也不用。個(gè)人覺(jué)得兩種方法都掌握會(huì)比較好哈，因?yàn)樵趯?shí)際中比較有應(yīng)用，所以也是比較?？嫉念}目。
???????????
來(lái)源：http://www./content-4-168251.html
|
