liaodong0812 @ 2022-01-01 23:04:54
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define NN 20000005
int a[NN];
int n;
void qsort(int left,int right) {
int i=left,j=right;
int mid=a[(i+j)/2];
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}
if(i<right)qsort(i,right);
if(j>left)qsort(left,j);
}
int main()
{
int k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
cin>>a[i];
}
qsort(1,n);
cout<<a[k+1];
return 0;
}
by shiroko2008 @ 2022-01-02 09:20:36
@liaodong0812 O(nlogn)会TLE,请用O(n)
by liaodong0812 @ 2022-01-02 22:39:47
@bugwriter 我就是想问怎么优化【捂脸】
by shiroko2008 @ 2022-01-03 10:52:06
1.找到一个基准点T
2.使T左边的元素小于等于T,右边大于T
3.根据T的下标与k-1的大小关系,选择在左边或右边递归
4.若T的下标=k-1,输出T,递归中止