std::nth_element可一步找到第K大元素，其将第(n−k)小元素置于正确位置，左右分区但不全排序，平均时间复杂度O(n)，注意索引换算和原数组是否可修改。
用 std::nth_element 一步到位，但要注意它不排序整个数组
想快速拿到第K大的元素，std::nth_element 是最直接的选择。它把第K个位置（按升序）“就位”，左边都 ≤ 它，右边都 ≥ 它，时间复杂度平均 O(n)，比全排序快得多。
注意：第K大 = 第 (n - k) 小（0-indexed），所以调用时要换算索引：
std::vector<int> arr = {3, 2, 1, 5, 6, 4};
int k = 2; // 求第2大 → 实际找升序下标为 arr.size() - k 的元素
std::nth_element(arr.begin(), arr.begin() + arr.size() - k, arr.end());- 调用后
arr[arr.size() - k]就是答案，但arr其他部分无序 - 如果原数组不能修改，得先拷贝一份再操作
- 最坏情况复杂度是 O(n²)，但实际中极少触发；若数据量极大且对最坏性能敏感，考虑堆方案
用 std::priority_queue 控制空间，适合流式或内存受限场景
当数组很大、或数据是陆续到达的（比如从文件/网络读取），用最小堆维护当前最大的 K 个数更稳妥。堆顶就是第K大元素。
关键点在于堆大小严格控制在 K，每次新元素比堆顶大才入堆：
立即学习“C++免费学习笔记（深入）”；
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
for (int x : arr) {
if (min_heap.size() < k) {
min_heap.push(x);
} else if (x > min_heap.top()) {
min_heap.pop();
min_heap.push(x);
}
}
// 循环结束，min_heap.top() 即为第K大- 堆方案时间复杂度 O(n log k)，空间 O(k)，k 远小于 n 时优势明显
- 别用
std::less<int>建最大堆——那样堆顶是最大值，没法筛出“第K大” - 初始化堆时如果
k > arr.size()，需提前判断，否则top()行为未定义
手写快排 partition 逻辑，理解本质且便于调试边界
很多面试题要求不依赖 STL，这时复现 nth_element 的核心逻辑——基于快排的 partition。它和 STL 版本一样只保证目标位正确，不排序其余部分。
重点在 pivot 选择和循环不变量设计。一个简洁可靠的实现要点：
- 用
rand() % (right - left + 1) + left随机选 pivot，避免退化 - partition 后返回的是 pivot 最终下标
p，比较p和目标索引target决定搜左还是右半段 - 目标索引仍是
n - k（升序第几小），不是k-1 - 递归改迭代可防栈溢出，但小数组直接递归更清晰
常见错误：混淆“第K大”和“降序第K位”
最常踩的坑是直接取 arr[k-1] 并假设数组已按降序排列——这既没排序也没保证正确性。
-
std::sort(arr.rbegin(), arr.rend())确实能得到降序结果，但 O(n log n) 不必要 - 误用
std::partial_sort：它把前 K 个排好序，但默认是升序，要指定std::greater<int>()才能拿到前 K 大，且仍比nth_element慢 - 当 k=1 时，有人写成
*max_element(...)——没错，但泛化性差；统一用nth_element或堆更一致
真正需要关注的是 k 的合法性检查、是否允许重复元素、以及原始数组能否修改——这些细节比算法本身更容易导致线上行为异常。
