BM46　最小的K个数¶

中等通过率 28.12%python3核心代码模式样例通过牛客 AC堆排序分治

牛客原题　源码

讲解章节：优先队列与堆

一句话

维护一个大小为 k 的大顶堆，堆顶是「已选的最大值」，谁更小就替掉它。

解题思路¶

这题考什么¶

直接排序取前 k 个是 O(n log n)，能过；但题面要的是 O(n log k)，做法是只让堆里始终装着「目前见过的最小的 k 个数」：

堆没满 k 个：直接放进去；
堆满了：拿新元素和堆顶（这 k 个里最大的那个）比，新元素更小就弹堆顶、放新元素；否则直接丢弃。

循环不变量：每处理完一个元素，堆里恰好是「已扫描前缀中最小的 min(k, 已扫个数) 个数」。扫完一遍，堆里就是全局最小的 k 个数。

因为要频繁取出「已选集合里的最大值」，需要的是大顶堆，而 Python 的 heapq 只提供小顶堆——标准技巧是存相反数： -x 最小即 x 最大，读取时再取一次负号还原。堆的性质与 heapq 的用法见优先队列与堆。

数据规模与复杂度¶

0 <= n,k <= 10000，0 <= val <= 1000，时限「其他语言 2 秒」。时间 O(n log k)，空间 O(k)——堆里永远只有 k 个数，与 n 无关，这也是它比「先排序再切片」更适合数据流场景的原因。（值域只有 0..1000，本题其实还能用 O(n + 1000) 的计数排序；堆解法胜在不依赖值域，是通用写法。）

坑在哪¶

要的是大顶堆，heapq 只有小顶堆，所以必须存相反数。直接拿小顶堆装 k 个数是错的：满员时该淘汰的是已选集合里最大的那个，而小顶堆弹出的是最小的，等于把答案自己丢掉。
这题是多解的，meta.json 的 judge 给 BM46 配了 unordered（按集合比对）：题面写明「1,2,3,4(任意顺序皆可)」，示例 1 的说明也讲返回 [1,3,2,4] 同样正确。代码末尾的 sorted 只为输出好看，不是正确性要求；反过来说，也不要因为自己的输出顺序与样例不同就以为写错了。
k <= 0 直接返回空（示例 2 给的正是 k=0），否则后面的 len(heap) < k 恒不成立，堆一直是空的，取堆顶会 IndexError。k 超过数组长度时堆填不满，自然全部返回。
heapreplace 一次调整完成「弹出堆顶 + 压入新元素」，只做一趟下沉；写成 heappop 加 heappush 是两次 O(log k) 调整，结果相同但白做一半功。
比较写的是 -heap[0] > x（堆顶原值大于新值）。用 >= 也不影响答案，但会在等值时白做一次替换。

样例复核¶

[0,1,2,1,2] 取 k=3。前三个 0、1、2 直接入堆，堆内（原值）为 {0,1,2}，堆顶 2；第四个 1 < 2，替掉堆顶得 {0,1,1}，堆顶 1；第五个 2 不小于 1，丢弃。结果排序后是 [0,1,1]，与示例 3 一致——重复的 1 保留两个，说明本题不去重。

参考实现¶

solutions/nowcoder/BM46/sol.py
import heapq
from typing import List, Optional


class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        # k=0（示例 2）或空数组：没有可选的数，直接返回空，也避免后面取空堆的堆顶
        if k <= 0 or not input:
            return []
        heap: List[int] = []                 # 存相反数，用小顶堆模拟大顶堆
        # 一趟扫描；每步维持不变量「堆内是已扫前缀中最小的 min(k, 已扫个数) 个数」
        for x in input:
            # 堆没满：无条件收下，此时还谈不上淘汰
            if len(heap) < k:
                heapq.heappush(heap, -x)
            elif -heap[0] > x:               # 堆顶是已选 k 个里的最大值，比它小才值得换
                heapq.heapreplace(heap, -x)  # 一次调整完成「弹出 + 压入」，比两步快
        return sorted(-v for v in heap)      # 题目允许任意顺序，排序只为可读

BM46 最小的K个数¶