好久沒更新了，今天我又來了。一直看我文章的朋友可能會發(fā)現(xiàn)，我之前多次提到堆這個數(shù)據(jù)結(jié)構(gòu)，它可以幫助我們快速地在一堆數(shù)據(jù)中，找到符合某個條件的最大或者最小的元素。今天我們還是要來談?wù)撍?，沒辦法，它就是這么強(qiáng)大又好用。
來看這樣一道題目：給定K個排序好的鏈表，排序好合并到一個列表中去。
示例 1:
輸入: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
輸出: [1, 2, 3, 3, 4, 6, 6, 7, 8]
示例 2:
輸入: L1=[5, 8, 9], L2=[1, 7]
輸出: [1, 5, 7, 8, 9]
拿到這道題的第一感覺似乎也不是很難嘛，我們可以把所有元素加到一個列表里面去然后再排序，時間復(fù)雜度也不過是O(N?logN)。這里N是K個鏈表所有元素之和。
不過這么做的話，其實(shí)鏈表們排沒排序都一樣，既然題目告訴我們鏈表是排序好的，那它肯定是更優(yōu)解法的重要條件。我們得想辦法利用好這個條件。我們想要讓最終的列表排好序，那肯定要把所有元素里最小的元素放在前面。既然給我們的K個鏈表都是排好序的，那我們只要比較它們的第一個元素就能得到最終列表的最小元素里。拿到最小元素我們就添加到最終列表里，按照這個思路，我們在每一步都可以拿到K個鏈表中的最小元素，最后得到我們想要的結(jié)果。
那說到在K個元素中找最小的元素，我們又想到堆了。那我們再來盤一下用堆我們該怎么做：
- 把每個鏈表第一個元素插入到最小堆
- 從堆中取出最小的元素添加到結(jié)果列表中
- 再從拿出去的元素所在的那個鏈表中取出下一個元素放到堆中
- 重復(fù)第2步跟第3步，我們可以保證所有元素添加到了結(jié)果列表中且有序
就拿第一個例子來說，我們再來詳細(xì)討論一下這個過程。
給定的鏈表: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
-
在從每個鏈表中取出第一個元素時，我們的堆是這樣的：
-
我們會取出位于堆頂?shù)脑?，加入到合并的列表中，然后把這個元素所在鏈表中的的下一個元素加入到堆中：
-
那么，我們再次把堆頂?shù)脑厝〕龇诺浇Y(jié)果列表中，把下一個元素添加到堆中：
-
重復(fù)上面的步驟，取出堆頂元素加入到結(jié)果列表中，再把它的下一個元素加入到堆中。這里有兩個3，可以隨便選，但是要注意選了哪個就把哪個的下一個元素加到堆中，這個次序很重要。
最終我們就能得到一個排序好的列表啦！
public static ListNode merge(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((n1, n2) -> n1.value - n2.value);
// 把第一個元素添加到堆
for (ListNode root : lists)
if (root != null)
minHeap.add(root);
// 從最小堆中取出最小的元素并加入到結(jié)果中
// 如果它在鏈表中還有下一個元素，那么把它的這個下一個元素添加到堆中
ListNode resultHead = null, resultTail = null;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll();
if (resultHead == null) {
resultHead = resultTail = node;
} else {
resultTail.next = node;
resultTail = resultTail.next;
}
if (node.next != null)
minHeap.add(node.next);
}
return resultHead;
}
看看，這個問題有了堆這個數(shù)據(jù)結(jié)構(gòu)變得格外簡單，復(fù)雜度也得到了優(yōu)化！這里時間復(fù)雜度在O(N?logK)，而空間復(fù)雜度在O(K)。這就是我們常聽到的多路歸并算法的核心思想，以后再看到類似題目知道該怎么辦了吧？
最后的最后，我再強(qiáng)調(diào)下復(fù)習(xí)一下常見的數(shù)據(jù)結(jié)構(gòu)的重要性，會對我們解題大有幫助。就拿這道題來說，思路其實(shí)很簡單，但是如果不知道或者忘了堆的用法，這道題大概率只能想到把所有元素加入結(jié)果列表再排序，豈不可惜？
