快速选择算法通过三路划分定位第K大数原始下标：先构建值-下标配对数组，将target_pos转为n-k升序索引，递归划分后根据k与等于pivot区间[lt,gt]关系决定返回或继续搜索。
用C++实现快速选择算法定位第K大数值在原数组中的下标位置，需在分区过程中保留原始索引映射关系，不能只对值排序后取下标——否则无法区分重复值或保持位置一致性。
构建带索引的值-下标配对数组
定义 vector<pair<int, int>> 类型容器，将每个元素的值和原始下标一起存入，例如 {nums[i], i}。
这一步不可省略：若仅排序数值，遇到重复值（如 [3,3,3,1] 中第2大是3，但有三个可能下标）将无法唯一确定原始位置。
实现三路划分的快速选择主逻辑
方法一：递归版本（推荐初学理解）
立即学习“C++免费学习笔记（深入）”；
① 设当前处理区间为 [left, right]，随机选取一个 pivot 值（推荐用 nums[rand() % (right - left + 1) + left] 避免最坏退化）；
② 执行三路划分：将配对数组分为 < pivot、== pivot、> pivot 三段，返回等于 pivot 的左右边界 lt 和 gt；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
③ 若 k <= gt 且 k >= lt，说明第K大值就落在等于 pivot 的区间内，直接返回任一该区间内配对的原始下标（如 arr[lt].second）；
④ 否则根据K与区间边界关系，递归进入左段（k < lt）或右段（k > gt）继续查找。
注意：K 是“第K大”，对应升序排列后的下标为 n - k，所以初始调用时传入的 target_pos = 【n - k】（0-based），不是 k 本身。
完整可运行源码
#include <vector>
#include <utility>
#include <random>
#include <algorithm>
using namespace std;
int quickSelectIndex(vector<int>& nums, int k) {
int n = nums.size();
vector<pair<int, int>> arr;
for (int i = 0; i < n; ++i) arr.emplace_back(nums[i], i);
int target_pos = n - k; // 转为升序下标
return quickSelectHelper(arr, 0, n - 1, target_pos);
}
int quickSelectHelper(vector<pair<int, int>>& arr, int left, int right, int k) {
if (left == right) return arr[left].second;
default_random_engine gen;
uniform_int_distribution<int> dis(left, right);
int pivot_idx = dis(gen);
swap(arr[pivot_idx], arr[right]);
int pivot_val = arr[right].first;
int lt = left, gt = right, i = left;
while (i <= gt) {
if (arr[i].first < pivot_val) swap(arr[lt++], arr[i++]);
else if (arr[i].first > pivot_val) swap(arr[i], arr[gt--]);
else ++i;
}
if (k <= gt && k >= lt) return arr[k].second;
else if (k < lt) return quickSelectHelper(arr, left, lt - 1, k);
else return quickSelectHelper(arr, gt + 1, right, k);
}
