题解：AcWing 786 第k个数

【题目来源】

AcWing：786. 第k个数 - AcWing题库

【题目描述】

给定一个长度为 \(n\) 的整数数列，以及一个整数 \(k\)，请用快速选择算法求出数列从小到大排序后的第 \(k\) 个数。

【输入】

第一行包含两个整数 \(n\) 和 \(k\)。

第二行包含 \(n\) 个整数（所有整数均在 \(1\sim 10^9\) 范围内），表示整数数列。

【输出】

输出一个整数，表示数列的第 \(k\) 小数。

【输入样例】

5 3
2 4 1 5 3

【输出样例】

3

【算法标签】

《AcWing 786 第k个数》 #快速排序# #快速选择#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 100010;  // 定义数组最大容量int n, k;     // n: 数组元素个数, k: 要找的第k小的元素
int q[N];     // 存储数组元素// 快速选择算法：在数组q的[l,r]区间内寻找第k小的元素
int quick_sort(int l, int r, int k) {// 递归终止条件：区间只有一个元素时直接返回if (l == r) return q[l];// 分区过程int x = q[l], i = l - 1, j = r + 1;  // 选择最左元素作为基准while (i < j) {// 从左向右找第一个>=x的元素while (q[++i] < x);  // 从右向左找第一个<=x的元素while (q[--j] > x);  // 交换这两个元素if (i < j) swap(q[i], q[j]);}// 计算左半部分的元素个数int sl = j - l + 1;// 根据k的位置决定递归处理哪一部分if (k <= sl) return quick_sort(l, j, k);      // 第k小在左半部分else return quick_sort(j + 1, r, k - sl);  // 第k小在右半部分
}int main() {// 输入数据cin >> n >> k;for (int i = 0; i < n; i++) cin >> q[i];// 调用快速选择算法并输出结果cout << quick_sort(0, n - 1, k) << endl;return 0;
}

【运行结果】

5 3
2 4 1 5 3
3