合并Python中K排序列表的程序
假设我们有一些列表，这些列表已排序。我们必须将这些列表合并为一个列表。为了解决这个问题，我们将使用堆数据结构。因此，如果列表为[1,4,5]，[1,3,4]，[2,6]，则最终列表将为[1,1,2,3,4,4,5,6]。
为了解决这个问题，我们将遵循以下步骤-
n：=列表大小
堆：=一个新列表
对于每个索引i和列表行[i]，执行
将（row[0]，i，0）插入堆
如果行不为空，则
res：=一个新列表
当堆不为空时，执行
将列表[行，列+1]，行，列+1插入堆
num，row，col：=堆的顶部元素
在res的末尾插入num
如果col<列表的大小[行]-1，则
返回资源
让我们看下面的实现以更好地理解-
示例
import heapq
class Solution:
def solve(self, lists):
n = len(lists)
heap = []
for i, row in enumerate(lists):
if row:
heapq.heappush(heap, (row[0], i, 0))
res = []
while heap:
num, row, col = heapq.heappop(heap)
res.append(num)
if col < len(lists[row]) - 1:
heapq.heappush(heap, (lists[row][col + 1], row, col + 1))
return res
ob = Solution()lists = [[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]
print(ob.solve(lists))输入项
[[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]
输出结果
[1, 4, 4, 4, 8, 11, 11, 13, 14]