主要思路:借鉴堆、队列特点,构建新的有序结果
# merge the k sorted list # main idea: 将每个list放入队列,初始一个小顶堆,size为list个数,value为队列的首个元素,交替寻找最小值存储到新list中 import heapq from collections import deque nums = [[1,3,43], [16,29,89], [4, 33, 88, 100,1011]] # 队列化 queues = list(map(deque, nums)) heap = [] for i, q in enumerate(queues): heap.append((q.popleft(), i)) # 堆化,弹出最小值: heapq.heapify(heap) result = [] while heap: # 弹出最小元素 val, index = heapq.heappop(heap) result.append(val) # 找出弹出元素所在队列中的下一个元素,push到堆中,重复以上步骤 if queues[index]: new_num = queues[index].popleft() heapq.heappush(heap, (new_num, index)) result
参考:https://izsk.me/2019/03/02/%E5%90%88%E5%B9%B6K%E4%B8%AA%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84(python)/
标签:index,heapq,序列表,python,合并,queues,list,队列,heap From: https://www.cnblogs.com/demo-deng/p/16644450.html