用Python在线性时间内查找第k个最小元素的程序

假设我们有一个名为 nums 的数字列表，我们还有另一个值 k，我们必须找到列表中第 k 个（从 0 开始）最小的元素。我们必须O(n)平均及时解决这个问题。

因此，如果输入像 nums = [6, 4, 9, 3, 1] k = 2，那么输出将是 4，因为排序后的列表将像 [1, 3, 4, 6, 9] ，第 k 个最小元素是 4。

示例

让我们看看以下实现以获得更好的理解 -

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