nth_element 第 k 小

读完能做什么

• 能用 nth_element 找出第 k 小的元素，并说出它对应容器里的哪个下标。
• 能解释它只保证“这个位置上的元素就位、两侧的划分关系成立”，不保证两侧各自有序。
• 能验证 1 <= k <= n 之后再取结果，避免越界。
• 能算出第 k 大对应哪个下标，并用排序副本核对答案。

为什么需要它

题目常常只要求“第 k 小的数是多少”，并不要求把整组数据排好。如果只为了一个位置就把整组排序，多花的时间其实浪费了：

• sort 要 O(n log n)，把全部元素的顺序都安排好。
• 只找第 k 小，理想情况下扫一遍、做几次划分就够了，平均只要 O(n)。

“第 k 小”和“排好序”之间有一个中间状态：不必知道两侧各自的顺序，只要保证“第 k 个位置上是正确的那个人，左边都不比它大，右边都不比它小”。nth_element 正是做这件事的，它比 sort 便宜。

它是什么

一句话：nth_element(first, nth, last) 重新排列区间 [first, last)，使得 nth 这个位置上放的是“排序后本该放在这里”的元素，同时保证它左边的元素都不大于它、右边的元素都不小于它。

几个必须就地看懂的概念：

第 k 小对应下标 k - 1。 下标从 0 开始：第 1 小在下标 0，第 2 小在下标 1，第 k 小在下标 k - 1。所以调用时的中间参数是 v.begin() + (k - 1)。

中间参数是位置，不是数字。 nth_element 的第二个参数是一个迭代器 nth，不是整数 k。要把它写成 v.begin() + k - 1。

只保证划分，不保证有序。 调用后，nth 左边的元素都不大于它，右边的都不小于它，但左边内部、右边内部各自的顺序是任意的。标准只规定这两条性质，不规定具体排列。

它会修改数据。 nth_element 没有返回值，它直接改动区间里元素的顺序。

区间 [first, last)。 迭代器是“指向某个位置的游标”，v.begin() 指向第一个元素，v.end() 是尾后位置；两个位置组成左闭右开区间。细节见 容器、迭代器与区间。

适用场景：只关心某个名次上的值（比如中位数、第 k 小、第 k 大），不需要整组有序。使用时要 #include <algorithm>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

数据 [7, 2, 5, 1, 9]，求第 3 小：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {7, 2, 5, 1, 9};

    // 第 3 小对应下标 3 - 1 = 2
    nth_element(v.begin(), v.begin() + 2, v.end());

    cout << "第 3 小的数：" << v[2] << '\n';
    return 0;
}

输出：

第 3 小的数：5

逐行看：

• vector<int> v = {7, 2, 5, 1, 9}; 五个元素，下标 0 到 4。
• nth_element(v.begin(), v.begin() + 2, v.end()) 的中间参数是 v.begin() + 2，对应下标 2。
• 调用后下标 2 上的元素就是“第 3 小”。这组数据排序后是 1 2 5 7 9，第 3 小是 5，所以输出 5。
• 注意：我们只读了 v[2] 这一个位置，没有去读两侧的顺序。

一步步看变化

先看 [7, 2, 5, 1, 9] 排好序是什么样，再看 nth_element 之后哪些性质成立：

nth_element 之后，下标 2 一定是 5，并且下标 0、1 上的值都 <= 5，下标 3、4 上的值都 >= 5。把这条划分关系画出来：

graph LR
    left["下标 0 和 1 都小于等于 5"] --> mid["下标 2 第 3 小 值 5"]
    mid --> right["下标 3 和 4 都大于等于 5"]

用程序验证这两条性质：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {7, 2, 5, 1, 9};

    nth_element(v.begin(), v.begin() + 2, v.end());

    cout << "某次实测排列：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    cout << "下标 2 上的第 3 小：" << v[2] << '\n';
    cout << "左边两个都不大于它：" << (v[0] <= v[2] && v[1] <= v[2]) << '\n';
    cout << "右边两个都不小于它：" << (v[3] >= v[2] && v[4] >= v[2]) << '\n';
    return 0;
}

输出：

某次实测排列：1 2 5 7 9 
下标 2 上的第 3 小：5
左边两个都不大于它：1
右边两个都不小于它：1

“某次实测排列”这几个字很重要。 上面那行 1 2 5 7 9 是本机（GCC 16.2.0）这次运行的结果，看起来正好完全有序，但这只是巧合。标准不保证两侧各自有序，换一组数据就可能乱序。下面这组数据就能看出这一点：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {9, 1, 8, 2, 7, 3, 6, 4, 5};

    // 排序后是 1 2 3 4 5 6 7 8 9，第 4 小对应下标 4 - 1 = 3
    nth_element(v.begin(), v.begin() + 3, v.end());

    cout << "某次实测排列：";
    for (int x : v) cout << x << ' ';
    cout << '\n';
    cout << "下标 3 上的第 4 小：" << v[3] << '\n';
    cout << "左边都不大于它：";
    for (int i = 0; i < 3; i++) cout << v[i] << ' ';
    cout << '\n';
    cout << "右边都不小于它：";
    for (int i = 4; i < (int)v.size(); i++) cout << v[i] << ' ';
    cout << '\n';
    return 0;
}

输出：

某次实测排列：3 1 2 4 5 7 6 8 9 
下标 3 上的第 4 小：4
左边都不大于它：3 1 2 
右边都不小于它：5 7 6 8 9 

下标 3 上是正确的 4，左边 3 1 2 都 <= 4，右边 5 7 6 8 9 都 >= 4。但左边并不是 1 2 3，右边也不是 5 6 7 8 9——两侧各自没有排序。想得到完全有序的结果，还得再调用 sort。这也再次说明：本页输出里那行“某次实测排列”只是记录一次运行，不能当成标准保证。

逐项扩展核心操作

名次把重复项也算进去

数据里有重复值时，“第 k 小”是按排序后的位置数的，重复项各占一个名次：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {4, 2, 4, 1, 3};   // 有重复值

    // 排序后是 1 2 3 4 4，名次把重复项也算进去，第 3 小是 3
    nth_element(v.begin(), v.begin() + 2, v.end());
    cout << "第 3 小：" << v[2] << '\n';

    vector<int> sorted = v;
    sort(sorted.begin(), sorted.end());
    cout << "排序后核对：";
    for (int x : sorted) cout << x << ' ';
    cout << '\n';
    return 0;
}

输出：

第 3 小：3
排序后核对：1 2 3 4 4 

排序后 1 2 3 4 4，第 3 个位置是 3。两个 4 分别占第 4、第 5 名，所以第 3 小是 3 而不是 4。

用排序副本核对结果

nth_element 只保证目标位置的值，两侧排列不确定，所以验收时不要比对整段序列，而是：

1. 把原数据复制一份，用 sort 排好；
2. 比较“第 k 小的值”是否一致；
3. 检查划分性质（左边都不大于、右边都不小于）。

上面两个例子都是这样核对的：sort(sorted.begin(), sorted.end()) 得到完全有序的副本，用它确认 v[2] == sorted[2]。因为排序副本是确定的，而 nth_element 的排列不确定，所以只把目标值和划分性质当作验收条件。

第 k 大：换算成下标

第 k 大和第 k 小的关系是：n 个元素里，第 k 大就是第 n - k + 1 小，对应下标 (n - k + 1) - 1 = n - k。所以求第 k 大，调用 nth_element(v.begin(), v.begin() + (n - k), v.end())，再读 v[n - k]。例子见“动手检查”第 2 题。

什么时候选它、哪里容易错

先验证 1 <= k <= n。 调用前必须保证中间位置落在区间内。如果 k 超出范围，v.begin() + k - 1 就指向了区间外，属于未定义行为：

// 错误示例：k 超出范围，中间位置指到了区间外
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {7, 2, 5, 1, 9};        // n = 5

    int k = 8;                              // 8 > n，非法
    nth_element(v.begin(), v.begin() + k - 1, v.end());  // 越界，结果不确定
    cout << v[k - 1] << '\n';
    return 0;
}

这段能编译，但 v.begin() + 7 已经越过了 v.end()，是未定义行为，本页不给它写运行结果。正确做法是先检查：if (1 <= k && k <= (int)v.size())，再调用。

别把整段序列当成结果。 调用后只有 nth 这个位置是确定的，两侧的顺序不确定。要整段有序，得再 sort 一次（见 sort 排序）。

打印整段时必须标注。 想展示调用后的内容，就照本页那样写明“某次实测排列，标准不保证两侧有序”，不要把它当成固定结果。

复杂度是平均线性。 标准规定的是平均 O(n)：一般情况下扫几遍就够，但它不是无条件的“最坏 O(n)”。额外空间也不能想当然地认为一定是 O(1)：它需要做划分，额外开销依实现而定。

它比 sort 便宜，但只便宜在“少排了两侧”。 需要整段有序时，直接用 sort，不要“先 nth_element 再 sort”，那样反而多做了一遍工作。

选读。 nth_element 的内部做法和快速排序的划分很像：挑一个基准元素，把比它小和比它大的分到两边，只对包含目标位置的那一半继续划分。这也是它“平均线性、但两侧不保证有序”的原因。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {6, 1, 4, 2, 8};
nth_element(v.begin(), v.begin() + 1, v.end());
cout << v[1] << '\n';

第 2 题：修改代码

下面这段片段求的是第 3 小。请把它改成求第 2 大，让输出变成 7：

vector<int> v = {7, 2, 5, 1, 9};
nth_element(v.begin(), v.begin() + 2, v.end());   // 现在求第 3 小
cout << v[2] << '\n';

验证条件：先说出第 2 大对应下标几，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {6, 1, 4, 2, 8};
    nth_element(v.begin(), v.begin() + 1, v.end());
    cout << v[1] << '\n';
    return 0;
}

2

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {7, 2, 5, 1, 9};
    // 第 2 大：n = 5，对应下标 n - 2 = 3
    nth_element(v.begin(), v.begin() + 3, v.end());
    cout << v[3] << '\n';
    return 0;
}

7

立即练习

这道题要用数组、循环和本页的 nth_element。做完后请说明：为什么这道题用 nth_element 比 sort 更合适？如果题目要求“输出前 k 小的数并按从小到大排列”，还能只用 nth_element 吗？