Python算法题集_合并K个升序链表
- 题23：合并K个升序链表
- 1. 示例说明
- 2. 题目解析
- - 题意分解
- - 优化思路
- - 测量工具
- 3. 代码展开
- 1) 标准求解【双层循环】
- 2) 改进版一【列表排序】
- 3) 改进版二【堆排序】
- 4) 改进版三【分区海选】
- 4. 最优算法
本文为Python算法题集之一的代码示例
题23：合并K个升序链表
1. 示例说明
-
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
2. 题目解析
- 题意分解
- 本题为对多个排序链表进行合并
- 基本的解法是双层循环，外循环次数为所有元素个数，内循环为K次比较
- 优化思路
-
通常优化：减少循环层次
-
通常优化：增加分支，减少计算集
-
通常优化：采用内置算法来提升计算速度
-
分析题目特点，分析最优解
-
可以考虑采用堆结构来进行排序
-
可以采用分治法对多链表进行两两合并，化整为零，递归处理
-
可以用列表排序法进行简单排序
-
- 测量工具
- 本地化测试说明：LeetCode网站测试运行时数据波动很大，因此需要本地化测试解决这个问题
CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块- 本题本地化超时测试用例自己生成，详见【最优算法章节】
3. 代码展开
1) 标准求解【双层循环】
外层循环，内层最小值检测，依次将最小节点连接起来，性能自然不是最求目标
勉强通关，超过07%
import CheckFuncPerf as cfp
class Solution:
@staticmethod
def mergeKLists_base(lists):
ilen = len(lists)
if ilen < 1:
return None
res_head = ListNode(0)
tmpNode = res_head
blast = True
while blast:
blast, bNone = False, True
for iIdx in range(ilen):
if lists[iIdx]:
if bNone:
minVal, minidx, bNone = lists[iIdx].val, iIdx, False
else:
if lists[iIdx].val < minVal:
minVal, minidx, bNone = lists[iIdx].val, iIdx, False
if not bNone:
blast = True
tmpNode.next = lists[minidx]
lists[minidx] = lists[minidx].next
tmpNode = tmpNode.next
return res_head.next
result = cfp.getTimeMemoryStr(Solution.mergeKLists_base, alists)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
# 运行结果
函数 mergeKLists_base 的运行时间为 950.22 ms；内存使用量为 4.00 KB 执行结果 = 0
2) 改进版一【列表排序】
将所有节点均存入列表结构，通过列表排序，最后再连接起来，代码简洁，性能优异，但是内存O(n)
性能卓越，超越96%
import CheckFuncPerf as cfp
class Solution:
@staticmethod
def mergeKLists_ext1(lists):
ilen = len(lists)
if ilen < 1:
return None
list_node = []
for iIdx in range(ilen):
while lists[iIdx]:
list_node.append([lists[iIdx].val, lists[iIdx]])
lists[iIdx] = lists[iIdx].next
sort_list = sorted(list_node, key=lambda x: x[0])
for iIdx in range(len(sort_list)-1):
sort_list[iIdx][1].next = sort_list[iIdx+1][1]
sort_list[-1][1].next = None
return sort_list[0][1]
result = cfp.getTimeMemoryStr(Solution.mergeKLists_ext1, alists)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
# 运行结果
函数 mergeKLists_ext1 的运行时间为 913.20 ms；内存使用量为 992.00 KB 执行结果 = 0
3) 改进版二【堆排序】
应用堆队列heapq来进行最小值检测，代码相对简洁，性能还行
马马虎虎，超过72%
import CheckFuncPerf as cfp
class Solution:
@staticmethod
def mergeKLists_ext2(lists):
import heapq
res_head = ListNode(0)
tmpNode = res_head
buffmin = []
for iIdx in range(len(lists)):
if lists[iIdx] :
heapq.heappush(buffmin, (lists[iIdx].val, iIdx))
lists[iIdx] = lists[iIdx].next
while buffmin:
minval, minidx = heapq.heappop(buffmin)
tmpNode.next = ListNode(minval)
tmpNode = tmpNode.next
if lists[minidx]:
heapq.heappush(buffmin, (lists[minidx].val, minidx))
lists[minidx] = lists[minidx].next
return res_head.next
result = cfp.getTimeMemoryStr(Solution.mergeKLists_ext1, alists)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
# 运行结果
函数 mergeKLists_ext2 的运行时间为 958.21 ms；内存使用量为 4.00 KB 执行结果 = 0
4) 改进版三【分区海选】
使用递归设计，每次合并两个链表，直到最后合成总链表；这种方式类似分区海选，不是每个选手都要面对所有人，效率最高，资源最少
性能卓越，超越95%
import CheckFuncPerf as cfp
class Solution:
@staticmethod
def mergeKLists_ext3(lists):
def mergeTwoLists(link1, link2) -> ListNode:
res_head = ListNode(0)
tmpNode = res_head
while link1 and link2:
if link1.val < link2.val:
tmpNode.next = link1
link1 = link1.next
else:
tmpNode.next = link2
link2 = link2.next
tmpNode = tmpNode.next
tmpNode.next = link1 if link1 else link2
return res_head.next
def mergeSort(lists, left, right) -> ListNode:
if left == right:
return lists[left]
mid = (left + right) // 2
leftlink = mergeSort(lists, left, mid)
rightlink = mergeSort(lists, mid + 1, right)
return mergeTwoLists(leftlink, rightlink)
ilen = len(lists)
if ilen < 1:
return None
return mergeSort(lists, 0, ilen - 1)
result = cfp.getTimeMemoryStr(Solution.mergeKLists_ext3, alists)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
# 运行结果
函数 mergeKLists_ext3 的运行时间为 393.49 ms；内存使用量为 0.00 KB 执行结果 = 0
4. 最优算法
根据本地日志分析，最优算法为第4种mergeKLists_ext3
def generateOneLinkedList(data):
head = ListNode()
current_node = head
for num in data:
new_node = ListNode(num)
current_node.next = new_node
current_node = new_node
return head.next
def generateOneLinks(listlink):
result = []
for iIdx in range(len(listlink)):
result.append(generateOneLinkedList(listlink[iIdx]))
return result
iLen, k = 100000, 10
listnums = []
for iIdx in range(k):
tmpNums = [x*(iIdx+1) for x in range(iLen)]
listnums.append(tmpNums)
alists = generateOneLinks(listnums)
result = cfp.getTimeMemoryStr(Solution.mergeKLists_base, alists)
print(result['msg'], '执行结果 = {}'.format(result['result'].val))
# 算法本地速度实测比较
函数 mergeKLists_base 的运行时间为 950.22 ms；内存使用量为 4.00 KB 执行结果 = 0
函数 mergeKLists_ext1 的运行时间为 913.20 ms；内存使用量为 992.00 KB 执行结果 = 0
函数 mergeKLists_ext2 的运行时间为 958.21 ms；内存使用量为 4.00 KB 执行结果 = 0
函数 mergeKLists_ext3 的运行时间为 393.49 ms；内存使用量为 0.00 KB 执行结果 = 0
一日练，一日功，一日不练十日空
may the odds be ever in your favor ~
