Leetcode:Merge k Sorted Lists分析和实现
题目大意是传入一个链表数组lists,每个链表都由若干个链接的链表结点组成,并且每个链表结点记录一个整数。题目保证传入的链表中的整数按从小到大进行排序。
题目要求我们输出一个新的链表,这个链表中应该包含所有在lists中出现的整数,并且按从小到大排序。
我的思路:
这个问题解法应该很多。我采用的解法是分治算法,灵感来自于归并排序,因为归并排序的递归完成后也会涉及到将两个有序数组重组合并。
首先说明如何重组两个链表为一个有序链表,其思路源自于我们在玩扑克牌时对两堆有序扑克牌进行排序的手法:
1.我们从两叠有序扑克牌(正面向上)中,选取最小的牌面(即两叠扑克牌盖在最上面的两张牌中较小的牌),并加入到手牌中。
2.循环上一步直到有一叠牌被完全取走。
3.将剩下的一叠牌全部按序加入到手牌中。
由于始终选取较小的牌,以及两叠牌的从小到大排序的性质,能保证剩余的牌总是会不小于被选走的手牌。假设两叠牌共n张,由于这个过程中每次都会使得桌上的牌减少1,而减少到0时就会必定结束,因此上面的步骤最多只会执行n次,这n次中每一次都涉及一次比较和取牌(在计算机中是常量时间),因此我们可以认为要合并两个有序牌堆的时间复杂度为O(n)。
combine(A, B):
ai = 0, bi = 0
al = A.length, bl = B.length
result = empty-list
while(ai < al && bi < bl)
if(A[ai] <= B[bi])
insert A[ai] into result
ai = ai + 1
else
insert B[bi] into result
bi = bi + 1
while(ai < al)
insert A[ai] into result
ai = ai + 1
while(bi < bl)
insert B[bi] into result
bi = bi + 1
return result
但是题目已经指出了,k:=lists.length不一定为2。因此我们要通过分治算法将需要合并的链表数减少为2。其思路是先合并下标为0~k/2的链表,在合并k/2~k的链表。最后利用我们上面所说的洗牌算法将两个链表合并。
rec(lists, from, to) //合并lists[from], ... lists[to - 1]为一个链表,并返回合并的链表
if(from + 1 == to)
return lists[i]
half = (from + to) / 2
part1 = rec(lists, from, half)
part2 = rec(lists, half, to)
return combine(part1, part2)
上面就是我们归并算法的完整实现。先说明它能返回正确的结果。当to - from == 1时,此时需要排序的链表只有一个,只要直接返回这个链表就可以了。因此当to - from == 1时这个算法是正确的。假设当to-from<p时(p >1),这个算法能返回正确的结果。那么当to-from=p时,函数将排序lists中from~half段和half~to段的链表委托给递归函数。由于from < half < to,因此half-from<to-from=p,to-half<to-from=p,因此递归函数对于部分的排序返回了正确的结果,分别记为part1,part2,part1中保存了from~half段的合并结果,而part2中保存了half~to段的合并结果。最终利用我们已经说明过的洗牌合并法对合并part1和part2,因此最终得到的结果则是lists[from], ... lists[to - 1]的有序合并结果。这里用了一个关键的想法,即合并顺序不会改变最终结果。利用数学归纳法我们可以得出对于任意to-from>=1,rec函数都能返回正确的结果。
接下来说明这个算法的复杂度。
首先空间复杂度应该是O(n),因为函数递归发生在空间分配之前,因此当函数从下级递归中跳出时,最多持有与lists中保存的整数的拷贝(保存在part1和part2中),在combine函数中又会分配一次空间,但也最多只是part1和part2的长度的加总,因此,rec函数同时占据的空间量不会超过2n=O(n)。再提一下,这里由于没有要求我们不能使用传入的链表,因此假如我们直接通过操作链表进行排序而不分配额外的空间,那么空间复杂度就可以被优化到O(1)。
时间复杂度我们必须展开来看。一种简明的方式是将不同的递归深度区分开来 ,在同一递归深度中的时间复杂度为O(n)。比方说在第一级递归,我们对长度为k的lists进行合并,但是实际上发生在这一递归深度的只有调用combine的合并操作,其时间复杂度为O(n)。同样在第二级递归,我们分别对0~k/2和k/2~k进行排序,而发生在这一递归深度的实际的操作只有combine操作,两个combine操作正好涉及了lists[0~k]中所有的元素,因此时间复杂度也是O(n)。考虑到递归深度最大为log2(k),因此总的时间复杂度为O(n)*log2(k)=O(nlog2(k))。
最后提供一下java代码,13ms AC:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length <= 1) { return lists.length == 0 ? null : lists[0]; } return mergeKLists(lists, 0, lists.length); } public ListNode mergeKLists(ListNode[] lists, int from, int to) { if (to == from + 1) { return lists[from]; } int half = (from + to) / 2; ListNode part1 = mergeKLists(lists, from, half); ListNode part2 = mergeKLists(lists, half, to); if (part1 == null || part2 == null) { return part1 == null ? part2 : part1; } if (part1.val > part2.val) { ListNode tmp = part1; part1 = part2; part2 = tmp; } ListNode traceNode1 = part1; ListNode traceNode2 = part2; ListNode formerNode1 = null; ListNode formerNode2 = null; while (traceNode1 != null && traceNode2 != null) { while (traceNode1 != null && traceNode2 != null && traceNode1.val <= traceNode2.val) { formerNode1 = traceNode1; traceNode1 = traceNode1.next; } ListNode start = traceNode2; while (traceNode1 != null && traceNode2 != null && traceNode2.val <= traceNode1.val) { formerNode2 = traceNode2; traceNode2 = traceNode2.next; } if (formerNode1 != null) { formerNode1.next = start; formerNode1 = formerNode2; } if (formerNode2 != null) { formerNode2.next = traceNode1; formerNode2 = null; } } return part1; } }
最新文章
- JavaScript权威设计--jQuery,Ajax.animate,SVG(简要学习笔记二十)[完结篇]
- FineUI(专业版)v3.0.0 发布,手机、平板和桌面全支持!
- 一篇学习HTTP状态码的神文:我与依依的橙色岁月
- C#: 异步委托
- iPhone开发中的技巧整理
- FindMe
- ASP.NET MVC- Controllers and Routing- Routing
- 深入解析spring中用到的九种设计模式
- Android项目---快递查询
- 神奇的background
- 好久没用IJ写Java 之 《求输入的一个数中包含奇数、偶数、零的个数》
- GlusterFS分布式文件系统的使用
- RT-thread内核对象--事件集
- 详解BOM用途分类及在汽车企业中的应用
- 【linux应用】将一个大文件按行拆分成小文件
- C#使用BeginInvoke和EndInvoke异步下载和获取返回结果
- Unity3D游戏开发——编程实现游戏管理器
- dwr3实现消息精确推送详细步骤
- The configuration file &#39;appsettings.json&#39; was not found and is not optional
- ACM-ICPC 2018 沈阳赛区网络预赛 Solution