PythonでKソートされたリストをマージするプログラム

いくつかのリストがあるとすると、これらのリストはソートされています。これらのリストを1つのリストにマージする必要があります。これを解決するために、ヒープデータ構造を使用します。したがって、リストが[1,4,5]、[1,3,4]、[2,6]の場合、最終的なリストは[1,1,2,3,4,4,5,6]になります。 。

これを解決するには、次の手順に従います-

• n：=リストのサイズ
• ヒープ：=新しいリスト
• インデックスiとリストの行[i]ごとに、
  を実行します。
  • 行が空でない場合、
    • ヒープに（row [0]、i、0）を挿入します
• res：=新しいリスト
• ヒープが空でない間は、
  • num、row、col：=ヒープの最上位要素
  • resの最後にnumを挿入
  • if col<リストのサイズ[行]-1、then
    • リスト[row、col + 1]、row、col+1をヒープに挿入
• return res

理解を深めるために、次の実装を見てみましょう-

例

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]