पायथन में रैखिक समय में kth सबसे छोटा तत्व खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है, हमारे पास एक और मूल्य k भी है, हमें सूची में kth (0 से शुरू) सबसे छोटा तत्व खोजना होगा। हमें इस समस्या को औसतन O(n) समय में हल करना है।

इसलिए, यदि इनपुट संख्या =[6, 4, 9, 3, 1] k =2 की तरह है, तो आउटपुट 4 होगा, जैसा कि सूची को छांटने के बाद [1, 3, 4, 6, 9] जैसा होगा। , k वां सबसे छोटा तत्व 4 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• maxHeap :=एक नया खाली ढेर
• 0 से k की सीमा में i के लिए, करें
  • अंक डालें[i] maxHeap में
• i के लिए k + 1 से लेकर अंकों के आकार -1 तक के लिए
  • यदि अंक [i]> अधिकतम ढेर [0], तो
    • maxHeap से शीर्ष हटाएं
    • अंक डालें[i] maxHeap में
• मैक्सहीप लौटाएं[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