BM46. 最小的K个数
题目描述
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。 返回顺序任意即可。
输入格式
input：int 型一维数组；k：int 型，需要取出的个数。
输出格式
返回 int 型一维数组，包含最小的 k 个数（任意顺序）。
示例
示例 1
输入：
input = [4,5,1,6,2,7,3,8], k = 4
输出：
[1,2,3,4]
说明：
最小的 4 个数是 1、2、3、4，返回 [1,3,2,4] 也可以。
示例 2
输入：
input = [1], k = 0
输出：
[]
说明： k 为 0 时返回空数组。
示例 3
输入：
input = [0,1,2,1,2], k = 3
输出：
[0,1,1]
说明： 不去重，两个 1 都算在内。
解题思路
第一步：理解问题本质
要从数组里取最小的 k 个。「最小」意味着我们关心的是相对大小， 而不是全序，所以没必要把整个数组排好序。
第二步：排序取前 k 个
最简单：
return sorted(input)[:k]
O(n log n)，能过，但当 k 远小于 n 时有点浪费 —— 我们只关心「最小的 k 个」， 剩下的顺序根本无所谓。
第三步：大顶堆维护 k 个候选（推荐）
用一个大顶堆装「目前见过的最小的 k 个元素」，堆顶就是这 k 个里最大的。
- 先用前 k 个元素建堆；
- 遍历剩下的每个元素 x：只要
x < 堆顶，就说明 x 比当前 k 个里最大的还小， 应该把堆顶淘汰、换成 x； - 遍历结束后，堆里正好是最小的 k 个。
复杂度 O(n log k)。Python 的 heapq 是小顶堆，存负值即可当大顶堆用。
快速选择（quickselect）也可以做到平均 O(n)，思路与 BM47 相同。
完整代码实现
算法可视化 · 逐帧回放这道题的代码15 帧 · 录制输入 [4,5,1,6,2,7,3,8], 4
from typing import List
import heapq
class Solution:
def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
"""用大顶堆维护最小的 k 个数（堆内用负数模拟大顶堆）"""
if k <= 0:
return []
if k >= len(input):
return list(input)
# 取前 k 个建大顶堆（存负值，堆顶是绝对值最大的 = 这 k 个里最大的）
heap = [-x for x in input[:k]]
heapq.heapify(heap)
for x in input[k:]:
if x < -heap[0]: # 比当前堆顶（k 个里最大的）还小 → 换掉它
heapq.heapreplace(heap, -x)
return [-x for x in heap]
示例推演
以 input = [4,5,1,6,2,7,3,8], k = 4 为例：
| 阶段 | 堆内元素（实际值） | 堆顶（最大） |
|---|---|---|
| 前 4 个建堆 | 4, 5, 1, 6 | 6 |
| 遇 2 | 2 < 6 → 换掉 6 | 4, 5, 1, 2 → 顶 5 |
| 遇 7 | 7 > 5 → 跳过 | 顶 5 |
| 遇 3 | 3 < 5 → 换掉 5 | 4, 3, 1, 2 → 顶 4 |
| 遇 8 | 8 > 4 → 跳过 | 顶 4 |
最终堆内是 1、2、3、4。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 排序 | O(n log n) | O(n) | 最简洁 |
| 大顶堆 | O(n log k) | O(k) | 推荐，k 小时更优 |
| 快速选择 | 平均 O(n) | O(1) | 最优但实现稍复杂 |
易错点总结
1. k 的边界
k <= 0 返回空数组，k >= n 返回全部元素。
这两条边界不处理，堆的构建或结果长度会出错。
2. Python 只有小顶堆
要模拟大顶堆必须存负值，取用时再取负回来，别直接拿 heap[0] 当最小值。
3. 把「去重」当成需求
题目明确说不去重，两个相同的值都算，所以不能用 set。
扩展思考
- 若数据流式到来、要求随时能取最小 k 个，堆的优势更明显（排序做不到）。
- 若要求第 K 大的「值」而不是「k 个数」，用快速选择即可（BM47）。