สมมติว่าเรามีบางรายการ รายการเหล่านี้จะถูกจัดเรียง เราต้องรวมรายการเหล่านี้เป็นรายการเดียว เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูลฮีป ดังนั้นหากรายการคือ [1,4,5], [1,3,4], [2,6] รายการสุดท้ายจะเป็น [1,1,2,3,4,4,5,6] .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของรายการ
- heap :=รายการใหม่
- สำหรับแต่ละดัชนี i และแถวของรายการ[i] ทำ
- ถ้าแถวไม่ว่างก็
- แทรก (แถว[0], i, 0) ลงในฮีป
- ถ้าแถวไม่ว่างก็
- res :=รายการใหม่
- ในขณะที่ฮีปไม่ว่าง ให้ทำ
- num, row, col :=องค์ประกอบด้านบนของฮีป
- ใส่ num ท้าย res
- ถ้า col <ขนาดของรายการ[row] - 1 แล้ว
- แทรกรายการ[row, col + 1], row, 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]
