Chương trình hợp nhất K danh sách đã sắp xếp bằng Python

Cho k danh sách đã sắp xếp, hợp nhất thành một danh sách đã sắp xếp. Sử dụng cấu trúc dữ liệu heap.

Ví dụ: [[1,4,5], [1,3,4], [2,6]] → [1,1,2,3,4,4,5,6].

Quy trình giải quyết (Min Heap)

1. Khởi tạo min-heap với phần tử đầu tiên của mỗi danh sách không rỗng: (value, list_index, element_index).
2. Trong khi heap không rỗng:
   • Lấy phần tử nhỏ nhất (num, row, col).
   • Thêm num vào kết quả.
   • Nếu col + 1 < len(lists[row]), đẩy phần tử tiếp theo của danh sách đó vào heap.
3. Trả về kết quả.

Ví dụ mã nguồn

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))
# Output: [1, 4, 4, 4, 8, 11, 11, 13, 14]

Đầu vào

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

Đầu ra

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