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++免费学习笔记（深入）”；
- 调用形式：
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>（默认最大堆），或显式写std::priority_queue<int, vector<int>, less<int>> - 初始化堆时，先插入前K个元素；之后对每个新元素，比较
num < pq.top()再决定是否替换 - 最后把堆中元素导出到数组——注意堆不保证内部有序，导出后需额外排序才能得到升序结果
- 时间复杂度
O(n log k)，空间仅O(k)，比前两种方法更省内存
常见错误与边界处理
实际写代码时，最容易栽在边界上，尤其是K为0、K等于数组长度、或数组为空这些情况。
-
k == 0：应直接返回空结果，否则nth_element或partial_sort会越界访问 -
k > n：多数人期望返回全部元素，但标准算法不自动截断，必须手动判断并设k = min(k, n) - 使用
vector<int>::iterator时，确保begin() + k不超过end()，否则触发 undefined behavior - 若数组含重复值，
nth_element和partial_sort都能正确处理，但“前K个最小”语义本身可能有歧义（比如第K小值有多个），需业务侧明确定义
真正麻烦的不是算法选哪个，而是 K 的合法性检查和结果提取方式——漏掉一次 if (k > vec.size()) k = vec.size(); 就可能在线上崩掉。
