17370845950

std::nth_element是求第k大元素的最优解，平均O(n)时间复杂度；需将第k大转为第n−k小，调用nth_element(arr.begin(), arr.begin()+n−k, arr.end())，之后arr[n−k]即为结果。

用 std::nth_element 最快求第k大元素

绝大多数场景下，别手写快速选择——C++ 标准库的 std::nth_element 就是为此设计的，平均时间复杂度 O(n)，原地操作，且经过高度优化。它把第 k 小的元素放到位置 k 上（从 0 开始），其余元素不保证有序。

求“第k大”，只需转换为“第 n−k 小”：对大小为 n 的数组 arr，调用 std::nth_element(arr.begin(), arr.begin() + n - k, arr.end())，之后 arr[n - k] 就是答案。

• 注意：k 是从 1 开始计数的（即第 1 大、第 2 大……），所以索引要小心换算
• 如果数组是 vector，确保 k 满足 1 ，否则行为未定义
• 该函数不保证其他元素有序，仅保证分区：左侧 ≤ 目标值，右侧 ≥ 目标值

手写快速选择时 pivot 选法很关键

自己实现快速选择（QuickSelect）时，最常踩的坑不是逻辑错，而是 pivot 选得差导致退化成 O(n²)。比如总选首/尾元素作 pivot，在已排序或逆序数组上会崩。

• 推荐用三数取中（median-of-three）：取首、中、尾三元素的中位数作为 pivot
• 更稳妥可用 std::random_device 随机选下标，再 swap 到末尾参与划分
• 避免递归过深：对小规模子数组（如 size ）直接插入排序；对较大子问题，先处理较小段，再用尾递归优化处理较大段

注意 std::nth_element 的迭代器边界含义

它的签名是：std::nth_element(First, Nth, Last)，其中 [First, Last) 是左闭右开区间，Nth 必须在该区间内，且函数会把“第 std::distance(First, Nth) 小的元素”放到 Nth 位置。

常见错误写法：nth_element(v.begin(), v.begin()+k, v.end()) 想求第k大，结果求的是第k小——没做 n−k−1 转换。

vector arr = {3, 2, 1, 5, 6, 4};
int k = 2; // 求第2大 → 应该是第5小（索引4，因为size=6）
int n = arr.size();
std::nth_element(arr.begin(), arr.begin() + n - k, arr.end());
cout << arr[n - k] << endl; // 输出 5

性能差异：比 std::sort 快，但不如堆（小k时）

当 k 很小（如前3大）或很大（如后3小），用 std::priority_queue 维护大小为 k 的堆反而更快，时间复杂度 O(n log k)，且空间可控；而 std::nth_element 总是扫描整个范围。

• k == 1 或 k == n：直接用 *max_element/*min_element，常数级优化
• k 或 k >= n − log n：考虑堆方案，避免无谓全扫描
• 通用情况（k 在中间范围）、或需多次查询不同 k：预排序或建树（如平衡BST）可能更合适

快速选择的“快”是有条件的——它省去了完全排序的代价，但所有元素至少被访问一次，这点容易被忽略。