AcWing 786. 第k个数
原题链接
简单
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int quick_sort(int a[], int l, int r, int k) {
if (l == r) return a[l];
int i = l - 1, j = r + 1, x = a[l];
while (i < j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
int s = j - l + 1; // 左边有几个数
// 翻译:如果左边的数的个数大于等于k,那么该数一定在左边的第k个
// 否则该数一定在右边的第k - s个
if (s >= k) return quick_sort(a, l, j, k);
else return quick_sort(a, j + 1, r, k - s); // 这个k - s是最关键的!
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int res = quick_sort(a, 0, n - 1, k);
cout << res << endl;
return 0;
}