โปรแกรมค้นหาองค์ประกอบที่เล็กที่สุดที่ k ในเวลาเชิงเส้นใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราก็มีค่า k อีกค่าหนึ่งเช่นกัน เราต้องหา kth (เริ่มจาก 0) องค์ประกอบที่เล็กที่สุดในรายการ เราต้องแก้ปัญหานี้โดยใช้เวลา O(n) โดยเฉลี่ย

ดังนั้น หากอินพุตเป็น nums =[6, 4, 9, 3, 1] k =2 ผลลัพธ์จะเป็น 4 เนื่องจากหลังจากจัดเรียงรายการจะเป็นเช่น [1, 3, 4, 6, 9] , องค์ประกอบที่เล็กที่สุดที่ k คือ 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• maxHeap :=ฮีปว่างใหม่
• สำหรับฉันในช่วง 0 ถึง k ทำ
  • แทรก nums[i] ลงใน maxHeap
• สำหรับฉันในช่วง k + 1 ถึงขนาดของ nums - 1 ทำ
  • ถ้า nums[i]> maxHeap[0] แล้ว
    • ลบด้านบนจาก maxHeap
    • แทรก nums[i] ลงใน maxHeap
• ส่งคืน 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