মান ল করুন কিছু লিস্ট, এই লিস্টগুলো সর্টেড। আমাদের এগুলোকে একটি লিস্টে মার্জ করতে হবে। এজন্য হিপ ডেটা স্ট্রাকচার ব্যবহার করব। তাই লিস্টগুলো [1,4,5], [1,3,4], [2,6] হলে ফাইনাল লিস্ট হবে [1,1,2,3,4,4,5,6]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- n := lists-এর আকার
- heap := একটি নতুন তালিকা
- lists-এ থাকা প্রতিটি ইনডেক্স i এবং row-এর জন্য:
- যদি row খালি না হয়, (row[0], i, 0) heap-এ পুশ করুন
- res := একটি নতুন তালিকা
- যখন heap খালি না হয়:
- num, row, col := heap-এর টপ এলিমেন্ট
- num কে res-এ অ্যাপেন্ড করুন
- যদি col < lists[row]-এর আকার - ১, lists[row][col+1], row, col+1 heap-এ পুশ করুন
- 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]
