用 Python 编写一个在线性时间内查找第 k 个最小元素的程序
pythonserver side programmingprogramming更新于 2026/1/21 21:00:17
假设我们有一个名为 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
打印 下一节:Python Pandas - 如何对指定频率的 DateTimeIndex 执行 ceil 操作 ❯❮ 上一节:Python Pandas - 如何以微秒频率对 DateTimeIndex 执行 ceil 运算
- 如果 nums[i] > maxHeap[0]，然后
