AcWing 786. 第k个数
原题链接
简单
#include<iostream>
using namespace std;
const int N = 100010; // 定义数组的最大长度
int n, k; // n 是数组的长度,k 是要查找的第 k 小的元素
int q[N]; // 定义数组 q,用于存储输入的数据
// 非递归快速选择算法,用于查找数组 q 中的第 k 小的元素
int quick_select(int l, int r, int k) {
// 当左右指针不相等时继续循环
while (l < r) {
int x = q[l], i = l - 1, j = r + 1; // 选择区间的第一个元素作为枢轴,初始化 i 和 j
// 分区操作,将小于枢轴的元素放到左边,大于枢轴的放到右边
while (i < j) {
while (q[++i] < x); // 从左往右找到第一个不小于枢轴的元素
while (q[--j] > x); // 从右往左找到第一个不大于枢轴的元素
if (i < j) swap(q[i], q[j]); // 交换这两个元素的位置
}
int sl = j - l + 1; // 计算左区间(包括枢轴)中的元素数量
if (k <= sl) { // 如果第 k 小的元素在左区间
r = j; // 更新右指针到左区间的边界
} else { // 如果第 k 小的元素在右区间
l = j + 1; // 更新左指针到右区间的开始
k -= sl; // 更新 k 的值,减去左区间的元素数量
}
}
return q[l]; // 当左右指针相等时,返回第 k 小的元素
}
int main() {
cin >> n >> k; // 读取数组的长度和第 k 小的元素的位置
for (int i = 0; i < n; i++) cin >> q[i]; // 读取数组的元素
cout << quick_select(0, n - 1, k) << endl; // 输出第 k 小的元素
return 0; // 程序结束
}