??????????????? 原題鏈接:?http://oj./problems/merge-k-sorted-lists/?
這道題目在分布式系統(tǒng)中非常常見，來自不同client的sorted list要在central server上面merge起來。這個題目一般有兩種做法，下面一一介紹并且分析復雜度。 第一種做法比較容易想到，就是有點類似于MergeSort的思路,就是分治法，不了解MergeSort的朋友，請參見歸并排序-維基百科，是一個比較經(jīng)典的O(nlogn)的排序算法，還是比較重要的。思路是先分成兩個子任務，然后遞歸求子任務，最后回溯回來。這個題目也是這樣，先把k個list分成兩半，然后繼續(xù)劃分，知道剩下兩個list就合并起來，合并時會用到Merge?Two Sorted Lists這道題，不熟悉的朋友可以復習一下。代碼如下：? 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;}
我們來分析一下上述算法的時間復雜度。假設總共有k個list，每個list的最大長度是n，那么運行時間滿足遞推式T(k) = 2T(k/2) O(n*k)。根據(jù)主定理，可以算出算法的總復雜度是O(nklogk)。如果不了解主定理的朋友，可以參見主定理-維基百科?？臻g復雜度的話是遞歸棧的大小O(logk)。
接下來我們來看第二種方法。這種方法用到了堆的數(shù)據(jù)結(jié)構(gòu)，思路比較難想到，但是其實原理比較簡單。維護一個大小為k的堆，每次取堆頂?shù)淖钚≡胤诺浇Y(jié)果中，然后讀取該元素的下一個元素放入堆中，重新維護好。因為每個鏈表是有序的，每次又是去當前k個元素中最小的，所以當所有鏈表都讀完時結(jié)束，這個時候所有元素按從小到大放在結(jié)果鏈表中。這個算法每個元素要讀取一次，即是k*n次，然后每次讀取元素要把新元素插入堆中要logk的復雜度，所以總時間復雜度是O(nklogk)?？臻g復雜度是堆的大小，即為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ù)據(jù)結(jié)構(gòu)也不用。個人覺得兩種方法都掌握會比較好哈，因為在實際中比較有應用，所以也是比較?？嫉念}目。
???????????
來源：http://www./content-4-168251.html
|
