【深基9.例4】求第 k 小的数

题意

给出 n 个数，最小的数编号为第 0 小，要求输出第 k 小的数。

思路

Python 竞赛中最稳的写法是先排序：

python

1
2numbers.sort()
print(numbers[k])

排序后，列表下标 0 是最小值，下标 k 正好是第 k 小。题面希望练习分治选择算法，但在本 Python 教学题单中，这题用来练习大量整数读入和内置排序。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：list.sort() 原地升序排序。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：大量整数输入使用 sys.stdin.buffer.read()。
Python 列表下标从 0 开始，正好对应题目的“第 0 小”。

代码

python

1
2
3
4
5
6
7
8
9
10import sys


data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
k = data[1]
numbers = data[2:2 + n]
numbers.sort()

print(numbers[k])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000005;

int n, k;
int a[MAXN];

// 快速选择：在 a[l..r] 中找第 k 小的数
int quick_select(int l, int r, int k) {
    if (l == r) return a[l];

    // 选第一个元素作为基准
    int pivot = a[l];
    int i = l, j = r;

    while (i < j) {
        // 从右往左找第一个小于 pivot 的数
        while (i < j && a[j] >= pivot) j--;
        // 从左往右找第一个大于 pivot 的数
        while (i < j && a[i] <= pivot) i++;
        if (i < j) swap(a[i], a[j]);
    }
    // 把基准放到正确位置
    swap(a[l], a[i]);

    // 基准的下标 i 就是第 i-l+1 小
    if (k == i - l + 1) return a[i];
    else if (k < i - l + 1) return quick_select(l, i - 1, k);
    else return quick_select(i + 1, r, k - (i - l + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    k++; // 题目第 0 小对应 C++ 第 1 小
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cout << quick_select(1, n, k) << "\n";

    return 0;
}

Pythonic 写法

sorted 第 k：

python

1
2
3import sys
data = list(map(int, sys.stdin.buffer.read().split()))
print(sorted(data[2:2 + data[0]])[data[1]])

STL 写法

这是 STL 写法：用 vector<ll> 装下全部数据，再调用 nth_element(v.begin(), v.begin() + k, v.end())，把第 k 小的数直接放到下标 k 上，最后输出 v[k]。它只保证这一个位置就位，两侧并不保证有序，所以平均只需 $O(n)$ ，比上面整体排序更适合“只问一个位置”的题目。注意题面写明最小的数是第 0 小，所以下标直接用 k，不用再减一；数据量接近 $5\times 10^6$ ，读入用 scanf 保证速度。

题面说“请尽量不要使用 nth_element”，那是希望读者手写分治选择算法；这份写法保留下来，书里也用它来和手写分治对拍，互相核对答案。

对应的 cppbook 章节：nth_element：确定第 k 小的元素

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 23:40
 * update_at: 2026-10-06 23:50
 */
// 这是 STL 写法：用 vector<ll> 装下全部数据，再用 nth_element 直接把第 k 小放到下标 k。
// 题面说“请尽量不要使用 nth_element”，那是希望读者手写分治选择算法；
// 这份写法保留下来，书里也用它来和手写分治对拍，互相核对答案。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> numbers; // 全部 n 个数；nth_element 需要随机访问迭代器，所以先把数据读全

int main() {
    ll n, k;
    // 数据量最大接近 5e6，用 scanf 快速读入
    scanf("%lld %lld", &n, &k);

    numbers.resize(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &numbers[i]);
    }

    // 题面里最小的数是第 0 小，所以第 k 小正好落在下标 k 上。
    // nth_element 只保证 numbers[k] 这个位置就位，两侧各自有序并不保证。
    nth_element(numbers.begin(), numbers.begin() + k, numbers.end());

    printf("%lld\n", numbers[k]);

    return 0;
}

复杂度

排序时间复杂度是 $O(n\log n)$ ，保存输入需要 $O(n)$ 空间。

总结

第 k 小可以用选择算法优化，但 Python 入门阶段先掌握“读入、排序、取下标”这条稳定路径。