【深基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]])

复杂度

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

总结

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

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

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结