std::nth_element不能直接交题，因它默认找第k小而非第k大，且会修改原容器顺序；求第k大须用nums.size()-k索引或greater()比较器，否则逻辑错误。
为什么 std::nth_element 不能直接拿去交题？
很多初学者看到 C++ 标准库有 std::nth_element，以为调用它就能“白嫖” O(n) 找第 K 大数——实际中常踩两个坑：它默认找第 K 小（不是第 K 大），且修改原容器顺序，副作用不可忽视。比如你在力扣上写 nth_element(nums.begin(), nums.begin()+k-1, nums.end())，得到的是第 k 小值；若要第 k 大，得传入 greater<int>()</int> 或手动换索引：用 nums.size() - k 作偏移。
手写快速选择必须处理的三个边界
自己实现 quickSelect 时，最容易崩在分区（partition）环节。常见错误包括：
- 左右指针越界未检查，比如
while (i 忘了 <code>i 判断，导致访问 <code>arr[-1] - 分区后 pivot 最终位置没和
right交换，而是和i或j盲交换，结果 pivot 不在正确位置 - 递归调用时区间开闭不一致，比如左半段写成
[left, i-1]，右半段却写成[i+1, right]，但实际分区后 pivot 在i，那左半段应是[left, i-1]，右半段是[i+1, right]—— 这个没问题；但若你用j作 pivot 位置，就得对应改右边界
推荐统一用 Lomuto 分区法：选 arr[right] 为 pivot，用 i 指向小于等于 pivot 的最右位置，循环结束后 swap arr[i] 和 arr[right]，返回 i。这样逻辑干净，不易错。
第 K 大 vs 第 K 小：索引别硬背，现场推
给定数组长度 n，求第 K 大数，等价于求升序排列后下标为 n - k 的元素（0-indexed）。但快速选择本身只保证“第 t 小”的位置正确，所以调用时目标索引是 t = n - k。不要记“第 K 大要改成 k-1”，而要每次写：「我要的数，在排好序后从 0 开始数是第几个？」
示例：
vector<int> nums = {3,2,1,5,6,4}; // n=6
k = 2 → 第 2 大是 5 → 升序后 [1,2,3,4,5,6]，下标是 4 → t = 6-2 = 4
调用 quickSelect(nums, 0, 5, 4);
</int>
随机化 pivot 是必须项，不是可选项
不随机选 pivot 时，快选退化成 O(n²)，比如对已排序数组找最小值，每次 pivot 都是最大值，每次只排除一个元素。C++ 中用 random_device + mt19937 初始化一次即可，不必每次 partition 都重置生成器。
关键代码片段：
int randIdx = left + uniform_int_distribution<int>(0, right - left)(rng); swap(arr[randIdx], arr[right]); </int>
注意：rng 应是函数外定义的静态或成员变量 mt19937，否则重复构造开销大，且可能因时间种子相同导致随机性失效。
真正难的不是写对算法，而是想清楚：你要的“第 K 大”在当前无序子数组里，对应的是“第几个小”。这个映射一旦错，后面全错。而且随机化 pivot 如果漏掉，本地小数据跑得飞快，一到大数据就超时，还很难复现。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
