注意细节即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<queue>
#include<iomanip>
using namespace std;
int n,k,ans;
int a[5000010];
long long read(){
long long x=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*h;
}
void q_sort(int l,int r){
if(l==r){
ans=a[l];
return ;
}
int mid=a[(l+r)>>1];
int i=l,j=r;
do {
while(a[i]<mid&&i<=j)i++; // detail 1
while(a[j]>mid&&i<=j)j--; // detail 2
if(i<=j){ // detail 3
swap(a[i],a[j]);
i++,j--;
}
}while(i<=j); // detail 4
// cout<<i<<","<<j<<":";
// for(int i=1;i<=n;i++){
// cout<<a[i]<<" ";
// }
// cout<<endl;
if(k==j+1){ // detail 5
ans=a[j+1];
return ;
}
else if(k<=j){ // detail 6
q_sort(l,j);
}
else {
q_sort(i,r); // detail 7
}
}
int main(){
// freopen("","r",stdin);
// freopen("","w",stdout);
n=read();k=read()+1;
for(int i=1;i<=n;i++)a[i]=read();
q_sort(1,n);
cout<<ans<<endl;
return 0;
}
注意细节!!!
或者使用函数:nth_element(a+start,a+question,a+end);
结果为:a[question]
Example:
int a[50]={0,1,2,3,4,5,6,7,8,9,10};
nth_element(a+1,a+10,a+11);
cout<<a[10]<<endl;
注意!此函数会把数组顺序打乱!