快速选择算法定位第K大值下标而非值本身，是因为需维护原始索引关系；正确做法是将值与原下标打包排序，分区仅比较值，最终返回对应下标的second字段。
快速选择算法为什么能定位第 K 大值的下标而不是值本身
快速选择（QuickSelect）默认返回的是第 K 小/大的值，但题目要求的是「所在位置」——即原始数组中该值的索引。关键点在于：不能对原数组做无痕排序或拷贝后丢弃索引映射，必须维护原始下标关系。
常见错误是直接对 std::vector<int></int> 排序或调用 std::nth_element，结果得到值却找不到它在原数组里的哪个 i。正确做法是把「值 + 原下标」打包成 pair 或结构体参与分区，且分区逻辑只比较值，不动下标。
- 用
std::vector<:pair int>></:pair>存储{value, original_index} - 分区时仅基于
pair.first比较，确保下标随值一起移动 - 当分区收敛到第 K 大位置时，直接取
arr[k].second即为原始下标 - 注意：第 K 大对应的是升序排列下的第
n - k小（0-indexed），别错算偏移
std::nth_element 能否直接用于找原始下标
可以，但必须传入自定义迭代器或包装后的容器，否则 std::nth_element 对纯 int 数组操作后，你无法回溯原位置。它不保存映射关系，只是重排当前内存块。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 不要对原始
std::vector<int></int>直接调用std::nth_element - 构造索引数组
indices，再用 lambda 作为比较器：[&nums](int i, int j) { return nums[i] - 调用
std::nth_element(indices.begin(), indices.begin() + k, indices.end(), comp)，完成后indices[k]就是原数组中第 K 小值的下标 - 若要第 K 大，则设目标位置为
indices.begin() + n - k（k 从 1 开始计数）
手写 partition 函数时 pivot 选错会导致 O(n²) 退化
平均复杂度 O(n) 的前提是每次分区都能把规模减半；最坏情况下（如每次选到最小/最大元作 pivot），递归深度变成 O(n)，每层扫描 O(n)，总复杂度 O(n²)。这在有序或近似有序数组上极易触发。
避免方法：
- 不用固定选
left或right，改用三数取中：median(nums[left], nums[mid], nums[right]) - 更稳妥用随机 pivot：
std::swap(nums[left], nums[left + rand() % (right - left + 1)]) - 务必在 partition 后检查返回的 pivot 下标是否等于目标位置，相等就立即返回，不继续递归
- 如果语言支持，优先用标准库
std::nth_element—— 它内部已做 pivot 随机化与 fallback 优化
完整可运行的 C++ 示例（返回第 K 大值原始下标）
#include <vector>
#include <random>
#include <algorithm>
<p>int quickSelectIndex(std::vector<int>& nums, int k) {
int n = nums.size();
// k-th largest → (n-k)-th smallest (0-indexed)
int target = n - k;</p><pre class='brush:php;toolbar:false;'>std::vector<std::pair<int, int>> arr;
for (int i = 0; i < n; ++i)
arr.emplace_back(nums[i], i);
int left = 0, right = n - 1;
std::random_device rd;
std::mt19937 gen(rd());
while (left <= right) {
// random pivot
std::uniform_int_distribution<> dis(left, right);
int p = dis(gen);
std::swap(arr[p], arr[right]);
// partition: move smaller elements to left
int i = left, j = right - 1;
while (i <= j) {
if (arr[i].first < arr[right].first) ++i;
else if (arr[j].first > arr[right].first) --j;
else std::swap(arr[i++], arr[j--]);
}
std::swap(arr[i], arr[right]);
if (i == target) return arr[i].second;
else if (i < target) left = i + 1;
else right = i - 1;
}
return -1; // shouldn't reach here}
这个实现返回的是原始下标，不是值；pivot 随机化防退化；partition 使用双指针避免重复交换；target 计算严格对应 K 大 → 升序第 n−k 位。实际使用时注意 k 的输入范围（1 ≤ k ≤ n），越界需提前校验。
真正容易被忽略的是：即使算法正确，若测试用例含重复值，多个相同数值可能分布在不同下标，此时「第 K 大」的定义依赖于排序稳定性——而快速选择不保证稳定，所以返回任意一个合法下标即可，无需纠结是哪一个。
