Chương trình hợp nhất danh sách được phân loại K bằng Python

Giả sử chúng ta có một số danh sách, các danh sách này đã được sắp xếp. Chúng tôi phải hợp nhất các danh sách này thành một danh sách. Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc dữ liệu heap. Vì vậy, nếu danh sách là [1,4,5], [1,3,4], [2,6], thì danh sách cuối cùng sẽ là [1,1,2,3,4,4,5,6] .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của danh sách
• heap:=một danh sách mới
• đối với mỗi chỉ mục i và hàng danh sách [i], thực hiện
  • nếu hàng không trống, thì
    • chèn (hàng [0], i, 0) vào heap
• res:=một danh sách mới
• trong khi heap không trống, hãy thực hiện
  • num, row, col:=phần tử trên cùng của heap
  • chèn num vào cuối res
  • nếu col
  • chèn danh sách [row, col + 1], row, col + 1 vào heap

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]

Đầu ra

[1, 4, 4, 4, 8, 11, 11, 13, 14]