AcWing 786. 第k个数
原题链接
简单
作者:
zicxr
,
2024-01-21 13:09:06
,
所有人可见
,
阅读 37
C++ 代码 第k个数 快选
#include<iostream>
using namespace std;
/*
快排
找到分界点 x l, r, l + r >> 1
左边所有数left <= x , 右边所有数 right >= x
递归排序left 递归排序right
快选
*/
const int N = 100010;
int n, k;
int a[N];
int Qsort(int l, int r, int k) {
if(l == r) return a[l]; // 若区间长度是1,这个数就是第k小
int x = a[l], i = l - 1, j = r + 1;
while(i < j) {
while(a[++ i] < x); // 划分
while(a[-- j] > x);
if(i < j) swap(a[i], a[j]);
}
int sl = j - l + 1; // 统计左边元素的个数
if(k <= sl) return Qsort(l, j, k); // k 小于等于 左边元素的个数, 则在左边
return Qsort(j + 1, r, k - sl); // 否则在右边
}
int main() {
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
printf("%d ", Qsort(0, n - 1, k));
return 0;
}
小伙不错,继续加油