std::nth_element 是查找前k个最小数（不排序）的最优方法，平均时间复杂度 o(n)，将第k小元素置于索引 k-1 处，左侧即为前k个最小数；需校验 k 的合法性，且操作不稳定。

用 std::nth_element 快速找到前K个最小数（不排序）

如果只需要找出前K个最小的数，但不要求它们有序，std::nth_element 是最优选择：平均时间复杂度 O(n)，比完整排序快得多，且原地操作、空间开销小。

它会把第K小的元素放到索引 k-1 位置，并保证其左侧所有元素 ≤ 它、右侧 ≥ 它——左侧恰好就是前K个最小数（顺序未定）。

• 调用形式：std::nth_element(vec.begin(), vec.begin() + k - 1, vec.end())
• K必须合法：若 k == 0 或 k > vec.size()，行为未定义；务必先校验
• 注意：nth_element 不稳定，相同值的相对顺序可能改变
• 若需保留原始数组，记得先拷贝一份再操作

用 std::partial_sort 获取有序的前K个最小数

当明确要求前K个数按升序排列时，std::partial_sort 是更直接的选择：它把最小的K个元素移到开头并排序，其余部分无序。

时间复杂度 O(n log k)，比全排序 O(n log n) 好，尤其当 k 时优势明显。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

• 调用形式：std::partial_sort(vec.begin(), vec.begin() + k, vec.end())
• 结果中 vec[0] 到 vec[k-1] 是升序排列的前K小值
• 如果 k == vec.size()，它退化为全排序，此时不如直接用 std::sort
• 和 nth_element 一样，它会修改原容器；若不可变，需提前复制

手写堆实现（适合超大数组或流式场景）

当数组太大无法全部加载进内存，或数据是动态到达的（比如日志流），就得用最大堆维护当前看到的K个最小值。

核心思路：用大小为K的最大堆存候选结果；每来一个新数，若小于堆顶就替换堆顶，再调整。最终堆内即为前K小。

• C++ 中可用 std::priority_queue<int></int>（默认最大堆），或显式写 std::priority_queue<int vector>, less<int>></int></int>
• 初始化堆时，先插入前K个元素；之后对每个新元素，比较 num 再决定是否替换
• 最后把堆中元素导出到数组——注意堆不保证内部有序，导出后需额外排序才能得到升序结果
• 时间复杂度 O(n log k)，空间仅 O(k)，比前两种方法更省内存

常见错误与边界处理

实际写代码时，最容易栽在边界上，尤其是K为0、K等于数组长度、或数组为空这些情况。

• k == 0：应直接返回空结果，否则 nth_element 或 partial_sort 会越界访问
• k > n：多数人期望返回全部元素，但标准算法不自动截断，必须手动判断并设 k = min(k, n)
• 使用 vector<int>::iterator</int> 时，确保 begin() + k 不超过 end()，否则触发 undefined behavior
• 若数组含重复值，nth_element 和 partial_sort 都能正确处理，但“前K个最小”语义本身可能有歧义（比如第K小值有多个），需业务侧明确定义

真正麻烦的不是算法选哪个，而是 K 的合法性检查和结果提取方式——漏掉一次 if (k > vec.size()) k = vec.size(); 就可能在线上崩掉。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！