std::nth_element可高效求第k大元素，平均o(n)时间、原地修改；降序第k大对应索引k-1并传std::greater()，升序下则取索引nums.size()-k。
用 std::nth_element 最快且最安全
直接改原数组、平均 O(n) 时间、不用手写堆或快排——std::nth_element 就是标准库为这问题准备的。它把第 K 大的数“拎”到指定位置，左边全是 ≥ 它的数，右边全是 ≤ 它的数，但左右内部不排序。
注意：K 是“第几大”，而 std::nth_element 操作的是“第几个位置”（从 0 开始），所以目标索引是 k - 1；但前提是你要查的是**降序意义下的第 K 大**，而默认是升序。所以得传 std::greater<int>()</int> 或手动换算索引：
- 升序排列下，第 K 大 = 索引
nums.size() - k处的元素（推荐，避免自定义比较符出错） - 调用前确保
0 ，否则越界未定义 - 该函数会修改原数组；如需保留原顺序，先拷贝一份
vector<int> nums = {3, 2, 1, 5, 6, 4};
int k = 2;
nth_element(nums.begin(), nums.begin() + nums.size() - k, nums.end());
// 此时 nums[nums.size() - k] 就是第 2 大的数：5
</int>
手写快速选择（QuickSelect）要防最坏 O(n²)
原理和快排分区一样，但只递归一半。问题在于：如果每次选的 pivot 都是最大/最小值（比如已排序数组 + 取首元素为 pivot），就会退化成 O(n²)。
- 务必随机化 pivot：用
random_shuffle或std::uniform_int_distribution选一个下标 swap 到末尾 - 分区后，只进左半段（当前 pivot 太大）或右半段（pivot 太小），别俩都递归
- 别漏掉相等元素的处理——分区时要把等于 pivot 的全归一边，否则可能死循环
示例关键逻辑（升序 partition，找第 K 大 → 目标位置 pos = n - k）：
int quickSelect(vector<int>& nums, int left, int right, int pos) {
int p = partition(nums, left, right); // 返回 pivot 最终下标
if (p == pos) return nums[p];
if (p > pos) return quickSelect(nums, left, p - 1, pos);
else return quickSelect(nums, p + 1, right, pos);
}
</int>
用 std::priority_queue 求第 K 大，空间换时间
适合流式数据或 K 很小的场景。建一个大小为 K 的小根堆，遍历数组：比堆顶大就弹顶、压入新数。最后堆顶就是第 K 大。
- 时间复杂度 O(n log k)，当 K nth_element 稍慢但更稳
- 必须用
priority_queue<int vector>, greater<int>></int></int>—— 默认是大根堆，那堆顶是最大值，没法留“前 K 大” - 初始化堆时别直接 push 所有数再 pop，应边读边维护大小，否则空间 O(n)
priority_queue<int vector>, greater<int>> pq;
for (int x : nums) {
pq.push(x);
if (pq.size() > k) pq.pop();
}
return pq.top(); // 第 K 大
</int></int>
边界与类型陷阱：k=1、重复元素、long long
线上题常卡这些点，本地测容易漏：
-
k == 1：直接*max_element最快，但nth_element同样适用，无需特判 - 数组含重复值（如
[2,2,2,1]，k=2）：第 2 大仍是 2，所有方法都天然支持，无需去重 - 元素范围超
int（如题目给long long）：确保容器类型、比较逻辑一致，别在priority_queue里混用int和long long - 输入为空或 k 越界：C++ 不抛异常，
nth_element行为未定义，务必前置校验
最易被忽略的是：用 nth_element 时误把 k 当作下标直接传进去，结果查成了第 K 小——记住，升序下第 K 大的位置永远是 n - k，不是 k - 1（除非你明确按降序调用）。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
