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

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

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

एल्गोरिदम (मैक्स हीप का उपयोग करके)

1. maxHeap := एक नया खाली हीप
2. i के लिए 0 से k तक:
   • nums[i] को maxHeap में डालें
3. i के लिए k+1 से len(nums)-1 तक:
   • यदि nums[i] < -maxHeap[0] (चूंकि पायथन का heapq मिन-हीप है, हम नेगेटिव मानों का उपयोग करते हैं):
     • maxHeap से टॉप हटाएं
     • nums[i] को maxHeap में डालें
4. -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))  # आउटपुट: 4

इनपुट

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

आउटपुट

4