Chương trình tìm phần tử nhỏ nhất thứ k trong thời gian tuyến tính bằng Python

Giả sử chúng ta có một danh sách các số gọi là nums, chúng ta cũng có một giá trị khác là k, chúng ta phải tìm phần tử nhỏ nhất thứ k (bắt đầu từ 0) trong danh sách. Trung bình chúng ta phải giải quyết vấn đề này trong O (n) thời gian.

Vì vậy, nếu đầu vào là nums =[6, 4, 9, 3, 1] k =2, thì đầu ra sẽ là 4, vì sau khi sắp xếp danh sách sẽ giống như [1, 3, 4, 6, 9] , phần tử nhỏ nhất thứ k là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• maxHeap:=một heap trống mới
• đối với tôi trong phạm vi từ 0 đến k, thực hiện
  • chèn nums [i] vào maxHeap
• đối với tôi trong phạm vi k + 1 đến kích thước là nums - 1, thực hiện
  • nếu nums [i]> maxHeap [0], thì
    • xóa hàng đầu khỏi maxHeap
    • chèn nums [i] vào maxHeap
• trả về maxHeap [0]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

4