可采用基于快速选择的索引感知变体，在平均O(n)时间内定位第K大数的原始索引：封装（值，索引）对同步分区，用三数取中选枢轴，迭代实现防栈溢出，三路分区处理重复值，严格保证第K大语义。
如果您需要在未排序的数组中定位第K大数值的原始索引位置（而非仅返回值），且要求平均时间效率优于O(n log n)，则可采用基于快速选择算法的索引感知变体。以下是实现该逻辑的具体步骤：
一、维护原始索引的分区划分
标准快速选择仅操作值，但定位原始位置需确保每次分区时索引与值同步移动。为此，将数组元素封装为（值，原始索引）对，在分区过程中同时重排二者，保证对应关系不丢失。
1、定义结构体或pair类型，存储每个元素的值及初始下标，例如：std::vector<:pair int>> arr_idx；
2、遍历原数组，将每个元素及其下标i存入arr_idx；
立即学习“C++免费学习笔记（深入）”；
3、对arr_idx执行快速选择分区，比较依据为pair.first（即值），交换操作同时作用于整个pair；
4、当分区定位到第K大值对应的位置时，直接返回该位置上pair.second（原始索引）。
二、使用三数取中法优化枢轴选取
避免最坏情况下的O(n²)时间开销，通过选取首、中、尾三元素的中位数作为枢轴，显著提升分区平衡性，使平均复杂度稳定趋近于O(n)。
1、在当前子区间[left, right]内，计算mid = left + (right - left) / 2；
2、比较arr_idx[left].first、arr_idx[mid].first、arr_idx[right].first三个值；
3、将中位数值对应的pair交换至right位置，作为本次分区的枢轴；
4、执行标准Lomuto或Hoare分区过程，保持索引与值绑定移动。
三、递归转迭代避免栈溢出
递归实现可能因深度过大引发栈溢出，尤其在极端不平衡分区时。改用显式栈模拟递归调用，仅压入待处理区间的左右边界，每次迭代处理一个子区间，空间复杂度降至O(log n)。
1、初始化std::stack<:pair int>> stk，并压入{0, n-1}；
2、循环弹出栈顶区间[left, right]，若left >= right则跳过；
3、对该区间执行一次分区，获取枢轴最终位置pivot_idx；
4、根据K与pivot_idx的关系，仅将需继续搜索的子区间（左段或右段）压入栈中。
四、处理重复值时的严格第K大语义
当存在多个相同数值时，“第K大”需按降序排列后严格占据第K个位置。若枢轴值重复出现，需扩展分区为三段（大于、等于、小于），并判断K落在哪一段，避免因相等值分布导致的偏移错误。
1、分区时维护三个指针：lt（小于区右界）、gt（大于区左界）、i（当前扫描位）；
2、扫描中将大于枢轴值的元素移至左侧，小于的移至右侧，等于的保留在中间；
3、获取等于区的范围[lt+1, gt-1]；
4、若K ∈ [lt+1, gt-1]，则第K大即为枢轴值，直接返回其中任一原始索引（如lt+1处）；
5、否则根据K与lt、gt的大小关系，决定向左段或右段递归搜索。
五、平均时间复杂度推导逻辑
每次分区以常数概率将问题规模至少缩小至原规模的3/4，设T(n)为期望运行时间，则满足递推式T(n) ≤ T(3n/4) + O(n)。由主定理或展开法可知，该式解为T(n) = O(n)。实际常数因子取决于枢轴质量，三数取中使常数项显著降低。
