合并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]