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

假设我们有一个名为 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))

输入

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

输出

4

更新于：19-10-2021

2K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始
广告