โปรแกรมรวม K ลิสต์ที่เรียงแล้วใน Python

สมมติว่าเรามีหลายลิสต์ที่เรียงแล้ว ต้องรวมเป็นลิสต์เดียว ใช้ Heap data structure

ตัวอย่าง: [[1,4,5], [1,3,4], [2,6]] ผลลัพธ์ [1,1,2,3,4,4,5,6]

ขั้นตอนการแก้ปัญหา (Min Heap)

1. n = len(lists)
2. heap = []
3. สำหรับแต่ละ i, row ใน lists:
   • ถ้า row ไม่ว่าง: ใส่ (row[0], i, 0) เข้า heap
4. res = []
5. วนลูป while heap:
   • num, row, col = heappop(heap)
   • เพิ่ม num เข้า res
   • ถ้า col < len(lists[row]) - 1: ใส่ (lists[row][col+1], row, col+1) เข้า heap
6. คืนค่า res

ตัวอย่างโค้ด Python

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]

อินพุต / เอาต์พุต

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

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