在Python中找到线性时间中的第k个最小元素的程序

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

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

要解决这个问题，我们将遵循以下步骤−

maxHeap：=一个新的空堆
对于范围从0到k的i，执行以下操作
- 将nums [i]插入maxHeap中
对于范围从k + 1到nums大小-1的i，执行以下操作
- 如果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））