给定一个未排序的整数顺序表，找出其中第 k 大的元素。例如序列 [3, 2, 1, 5, 6, 4] 中第 2 大的元素是 5。
题目
第 k 大元素
输入无序序列，输出第 k 大的元素值。
任务要求
- 从标准输入读入
n、k和序列元素； - 输出第
k大的元素值； - 鼓励实现平均
O(n)的快速选择算法，但先写一个正确版本（如排序后取值）再优化也可以接受。
输入格式
- 第一行：两个整数
n和k； - 第二行：
n个整数，表示无序顺序表。
输出格式
- 一行一个整数，表示第
k大的元素值。
数据范围与限制
| 项目 | 范围 |
|---|---|
序列长度 n | 1 ≤ n ≤ 10⁵ |
| k | 1 ≤ k ≤ n |
| 元素值 | −10⁹ ≤ 元素 ≤ 10⁹ |
| 时间复杂度要求 | 期望 O(n)，排序解法 O(n log n) 可作为起点 |
| 额外空间限制 | O(1) 或 O(log n)（递归栈） |
样例
样例输入 1
input
6 2
3 2 1 5 6 4样例输出 1
output
5样例输入 2
input
1 1
42样例输出 2
output
42样例输入 3
input
5 3
-1 -5 -3 -2 -4样例输出 3
output
-3样例解释
以样例 1 为例，输入 n=6, k=2, a=[3,2,1,5,6,4]：
目标是找升序排列后下标为 n-k=4 的元素（即第 5 小的元素）。
- 随机选
pivot=4，三向切分后：左侧[5,6]，中间[4]，右侧[3,2,1]； - 左侧有 2 个元素，
n-k=4不在左侧； - 中间有 1 个元素，2+1=3 < 4，也不在中间；
- 递归右侧
[3,2,1]，找下标4-3=1的元素； - 在
[3,2,1]中选pivot=2，切分后左侧[3]，中间[2]，右侧[1]； - 左侧 1 个元素，
1恰好等于目标下标，答案为5。
（实际执行中 pivot 选择是随机的，以上仅为一种可能路径。）
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。
powershell
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make scoreWindows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：
powershell
pnpm lab:doctor -- labs/chapter-01/exercise/E-01-03-sequential-list-kth-largest
pnpm lab:run -- labs/chapter-01/exercise/E-01-03-sequential-list-kth-largest
pnpm lab:run -- labs/chapter-01/exercise/E-01-03-sequential-list-kth-largest --case 001-sample
pnpm lab:score -- labs/chapter-01/exercise/E-01-03-sequential-list-kth-largestmake run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。
思考题
- 如果要求第
k大和第m大（k < m）同时输出，能否在一次快速选择中完成？ - 快速选择在什么输入下会退化到最坏情况 O(n²)？如何缓解？
题解
点击查看题解
思路
使用**快速选择（Quickselect）**算法，期望 O(n) 找到第 k 大元素。
核心思想与快速排序相同：选一个 pivot，将数组划分为大于、等于、小于三部分。但快速选择只递归包含答案的那一侧，因此期望复杂度为 O(n)。
算法步骤
- 将问题转化为找升序排列下标为
n - k的元素； - 随机选
pivot； - 三向切分：
> pivot放左边，== pivot放中间，< pivot放右边； - 若
n - k落在左侧区间，递归左侧；落在右侧，递归右侧；落在中间，直接返回pivot。
复杂度分析
- 期望时间复杂度：
O(n)，每次问题规模期望减半。 - 最坏时间复杂度：
O(n²)，极端不平衡的划分。 - 空间复杂度：
O(log n)，递归栈深度。
边界注意
- 随机选
pivot可极大降低退化为最坏情况的概率； k的范围保证1 <= k <= n，无需额外判断。
点击查看参考代码
cpp
#include <cstddef>
#include <iostream>
#include <vector>
struct EqualRange {
std::size_t first{};
std::size_t last{};
};
EqualRange partition_three_way(std::vector<long long>& a, std::size_t left, std::size_t right) {
const long long pivot = a[left + (right - left) / 2];
std::size_t less = left;
std::size_t current = left;
std::size_t greater = right;
while (current <= greater) {
if (a[current] < pivot) {
std::swap(a[less++], a[current++]);
} else if (a[current] > pivot) {
std::swap(a[current], a[greater--]);
} else {
++current;
}
}
return {less, greater};
}
long long quickselect(std::vector<long long>& a, std::size_t left, std::size_t right, std::size_t target) {
while (left < right) {
const EqualRange equal = partition_three_way(a, left, right);
if (target < equal.first) {
right = equal.first - 1;
} else if (target > equal.last) {
left = equal.last + 1;
} else {
return a[target];
}
}
return a[left];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::size_t n = 0, k = 0;
std::cin >> n >> k;
std::vector<long long> a(n);
for (auto& v : a) std::cin >> v;
std::cout << quickselect(a, 0, n - 1, n - k) << '\n';
}