AcWing 786. 第k个数
原题链接
简单
作者:
sybol
,
2021-09-28 09:36:40
,
所有人可见
,
阅读 168
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], n, k;
void quick_sort(int q[], int l, int r, int k){
if(l >= r) return;
int pivot = q[(l + r)/ 2], i = l - 1, j = r + 1;
while(i < j){
do i ++ ; while(q[i] < pivot);
do j -- ; while(q[j] > pivot);
if(i < j) swap(q[i], q[j]);//应该是<.
}
//if(j == k-1) return;不可乱改。从这里领略快排的要领,不到最后一刻,没有元素的位置是固定的。
if(j >= k-1) quick_sort(q, l, j, k);
else quick_sort(q, j + 1, r, k);
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 0; i < n; ++ i) scanf("%d", &q[i]);
quick_sort(q, 0, n - 1, k);
printf("%d", q[k-1]);
return 0;
}