AcWing 786. 第k个数
原题链接
简单
作者:
tgs
,
2021-01-04 10:22:36
,
所有人可见
,
阅读 425
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int partition(int q[], int l, int r) {
swap(q[l], q[rand() % (r - l + 1) + l]);
int p = l;
int lt = l + 1, gt = r;
while (true) {
while (lt <= r && q[lt] < q[p]) lt++;
while (gt >= l && q[gt] > q[p]) gt--;
if (lt > gt) break;
swap(q[lt++], q[gt--]);
}
swap(q[p], q[gt]);
return gt;
}
int quickSort(int q[],int l, int r, int k) {
while (true) {
int p = partition(q, l, r);
if (p == k) break;
else if (p < k) l = p + 1;
else r = p - 1;
}
return q[k];
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &q[i]);
printf("%d\n", quickSort(q, 0, n - 1, k - 1));
return 0;
}