একটি সংখ্যার তালিকা nums এবং একটি মান k দেওয়া আছে। লিস্টে k-তম (০-ইনডেক্সড) স্মলেস্ট এলিমেন্ট বের করতে হবে। গড়ে O(n) সময়ে সমাধান করতে হবে।
উদাহরণ: nums = [6, 4, 9, 3, 1], k = 2 হলে আউটপুট 4। সর্টেড লিস্ট: [1, 3, 4, 6, 9], ২-য় ইনডেক্সে ৪।
সমাধানের পদ্ধতি
ম্যাক্স হিপ (Max Heap) ব্যবহার করে O(n log k) সমাধান। k+1 আকারের ম্যাক্স হিপ রক্ষা করুন।
- প্রথম
k+1টি এলিমেন্ট হিপে डालুন (নেগেটিভ মান দিয়ে ম্যাক্স হিপ বানান)। - বাকি এলিমেন্টগুলো için: যদি বর্তমান এলিমেন্ট হিপের রুট (সর্বোচ্চ) থেকে ছোট হয়, তবে রুট বাদ দিয়ে বর্তমান এলিমেন্ট যোগ করুন।
- শেষে হিপের রুট (নেগেটিভ) হল
k-তম স্মলেস্ট।
পাইথন কোড
from heapq import heappop, heappush
def solve(nums, k):
maxHeap = []
# প্রথম k+1 টি এলিমেন্ট হিপে রাখুন
for i in range(k + 1):
heappush(maxHeap, -nums[i])
# বাকি এলিমেন্ট প্রক্রিয়া করুন
for i in range(k + 1, len(nums)):
if nums[i] < -maxHeap[0]: # হিপের রুট = -maxHeap[0]
heappop(maxHeap)
heappush(maxHeap, -nums[i])
return -maxHeap[0]
# টেস্ট
nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k)) # আউটপুট: 4বিকল্প: QuickSelect (গড়ে O(n))
import random
def quickselect(nums, k):
if len(nums) == 1:
return nums[0]
pivot = random.choice(nums)
lows = [x for x in nums if x < pivot]
highs = [x for x in nums if x > pivot]
pivots = [x for x in nums if x == pivot]
if k < len(lows):
return quickselect(lows, k)
elif k < len(lows) + len(pivots):
return pivot
else:
return quickselect(highs, k - len(lows) - len(pivots))
# টেস্ট
print(quickselect([6, 4, 9, 3, 1], 2)) # আউটপুট: 4সময় জটিলতা
হিপ সমাধান: O(n log k)। QuickSelect: গড়ে O(n), খারাপ কেস O(n²)।
