পাইথনে রৈখিক সময়ের মধ্যে kth ক্ষুদ্রতম উপাদান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে, আমাদের আরেকটি মান k আছে, আমাদের তালিকার সবচেয়ে ছোট উপাদান kth (0 থেকে শুরু করে) খুঁজে বের করতে হবে। আমাদের এই সমস্যাটি গড়ে O(n) সময়ে সমাধান করতে হবে।

সুতরাং, ইনপুট যদি nums =[6, 4, 9, 3, 1] k =2 এর মত হয়, তাহলে আউটপুট হবে 4, যেমন সাজানোর পরে তালিকাটি [1, 3, 4, 6, 9] এর মত হবে। , kth ক্ষুদ্রতম উপাদান হল 4।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• maxHeap :=একটি নতুন খালি হিপ
• আমি 0 থেকে k রেঞ্জের জন্য, কর
  maxHeap এ
  • সংখ্যা [i] সন্নিবেশ করান
• এর জন্য k + 1 থেকে সংখ্যার আকার - 1, do
  • যদি সংখ্যা[i]> maxHeap[0] হয়, তাহলে
    • maxHeap থেকে শীর্ষ মুছুন
    maxHeap এ
    • সংখ্যা [i] সন্নিবেশ করান
• ম্যাক্সহিপ ফেরত দিন[0]

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from heapq import heappop, heappush
def solve(nums, k):
   maxHeap = []
   for i in range(k + 1):
      heappush(maxHeap, -nums[i])
   for i in range(k + 1, len(nums)):
      if nums[i] < -maxHeap[0]:
         heappop(maxHeap)
         heappush(maxHeap, -nums[i])
   return -maxHeap[0]

nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k))

ইনপুট

[6, 4, 9, 3, 1], 2

আউটপুট

4