LeetCode 第23题 Merge k Sorted Lists【分而治之】【最小堆】(Java)

原题地址:https://leetcode.com/problems/merge-k-sorted-lists/

这道题的题目是合并k个有序的链表,标定难度为Hard,详细需求:

合并k个有序的链表,返回一个新的有序链表。

例子:

Input:

1->4->5,  

1->3->4,  

2->6

Output: 1->1->2->3->4->4->5->6

逻辑不复杂,合并k个有序链表,我想不出来怎么一次性合并k个链表,貌似也不是不可以,但是代码感觉有点乱。但是更简单的方法就是反正我们刚做过21题,所以我们知道怎么合并两个有序链表。我们就一次合并两个有序链表,最后合并完全部的链表。这道题我们提供暴力解法、分而治之以及最小堆三种解法。

暴力解法

思路很简单一个for循环一个一个链表的去合并。总共需要合并k-1次。代码里面直接调用了21题的mergeTwoLists方法

分而治之解法

分而治之怎么解这道题呢?其实大概一想就知道了,就是把问题分成两半,然后把子问题再分成两半,直到问题小到只剩两个链表,然后再返回一步一步合并结果。分析完了你会发现这个问题跟归并排序(Merge-Sort)的思路是一样的。所以,我们的解法就完全模仿了《算法导论》的归并排序的写法。那么复杂度也就是nlog(n).

最小堆解法

我们今天讨论了堆和堆排序算法。于是我给23题加入了一个用最小堆解决的方案。这里用的堆算法和《Leetcode专题 堆结构和堆排序》中提供的最大堆算法逻辑完全一样,只是最大换成最小而已。最大堆原理可以参看此文。

这段代码的思路是,首先把全部列表输入到数组里面,然后用数组构建一个最小堆,然后循环输出最小元素,串成一个链表输出。

你可以在Github代码里面看到包括最小堆实现的全部代码,这里只提供调用了我写的最小堆的代码的截图:

代码地址: https://github.com/tinyfool/leetcode/tree/master/src/p0023

这道题是分而治之,如果你对分而治之算法本身不太熟悉,请参阅《算法导论》。《算法导论》一书在2.3.1章节介绍了Merge Sort(归并排序),在第4章“分而治之”介绍了4.1 the maximum-subarray problem(最大子数组问题),4.2 Strassen’s algorithm for matrix multiplication (Strassen的矩阵乘法算法)。

也请参阅我的文章《LeetCode专题 分而治之》,文章中实现了算法导论里面的这三个分而治之的问题的代码,以及LeetCode相关问题的一个列表。

也请参阅《Leetcode专题 堆结构和堆排序》,文章介绍了堆和堆排序,以及最大堆的实现。本题我们实现了一个最小堆,跟最大堆原理一样,只需要做几行修改即可。

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据