C++ std::nth_element怎么快速找到第K大的数-C++-PHP中文网

std::nth_element比sort快，因为它只将第k个位置元素就位并保证左右分区有序性，不排序子区间，平均时间复杂度o(n)，而sort为o(n log n)；找第k大需换算为升序下索引n-k，且须校验k有效性。

c++ std::nth_element怎么快速找到第k大的数

std::nth_element 为什么能比 sort 快

因为 std::nth_element 只保证第 K 个位置（0-indexed）的元素就位，且左边所有元素 ≤ 它、右边所有元素 ≥ 它，不关心左右子区间的内部顺序。时间复杂度平均 O(n)，而 std::sort 是 O(n log n) —— 当你只关心“第 K 大”而非完整排序时，它就是更轻量的选择。

注意：它不返回值，而是原地重排容器，你要自己取索引位置的元素。

找第 K 大要传什么索引

默认是升序语义：调用后，nth_element(v.begin(), v.begin() + k, v.end()) 会让第 k 小的数落在 v[k]（0-indexed）。所以找第 K 大，得换算成升序下的第 (n−K) 小：

若容器大小为 n，第 1 大 → 索引 n-1；第 2 大 → n-2；第 K 大 → n-K
务必检查 K >= 1 && K ，否则 <code>n-K 会越界（比如 K=0 或 K > n）
常见错误：写成 v.begin() + K - 1 并假设这是第 K 大——那是第 K 小

示例（找第 2 大）：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

std::vector<int> v = {3, 1, 4, 1, 5, 9};
int n = v.size(); // 6
std::nth_element(v.begin(), v.begin() + n - 2, v.end());
// 此时 v[n-2] 就是第 2 大：v[4] == 5（实际运行后 v 可能为 {1, 1, 3, 4, 5, 9} 或其他合法排列）
</int>

要不要自定义比较器？

如果只是数值大小比较，不用；但如果你要找“第 K 大的绝对值”或按结构体某个字段排，就必须传比较器，而且要注意语义一致性：

找“最大”，比较器应返回 a > b（即降序逻辑），此时第 K 大直接对应 v.begin() + K - 1
但更推荐统一用升序 + 索引换算：保持比较器为 std::less{}（默认），然后索引仍用 n-K，避免混淆
错误示范：std::nth_element(..., std::greater{}) 后取 v[K-1] —— 这看似直觉，但一旦容器有重复值或你后续要复用逻辑，极易出错