欸嘿,典型的求解第k小的数的问题
算法中使用了快速排序
关键之处在于原本快排需要两边都进行排序,但现在我们只关心第k小的数,所以,如果在ll比k大那么就排左半边,比k小就比右半边,从而实现时间复杂度的下降
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 const int MAXN=5000005; 6 7 int n,k; 8 int a[2][MAXN]; 9 10 void read(int &p) 11 { 12 p=0;char s=getchar(); 13 while(!isdigit(s)) s=getchar(); 14 for(;isdigit(s);s=getchar()) p=p*10+s-‘0‘; 15 } 16 //利用快排 17 int sortx(int l,int r,int flag) 18 { 19 int tem=a[flag][(l+r)/2];int ll=l,rr=r; 20 //cout<<tem<<" "; 21 for(int i=l;i<=r;i++) 22 { 23 if(i==(l+r)/2) continue; 24 if(a[flag][i]<tem) a[flag^1][ll++]=a[flag][i]; 25 else a[flag^1][rr--]=a[flag][i]; 26 } 27 a[flag^1][ll]=tem; 28 //cout<<ll<<" "<<rr<<endl; 29 if(ll==k) return tem; 30 if(ll<k) return sortx(ll+1,r,flag^1); 31 else return sortx(l,ll,flag^1); 32 } 33 34 35 int main() 36 { 37 cin>>n>>k;k++; 38 for(int i=1;i<=n;i++) read(a[0][i]); 39 //for(int i=1;i<=n;i++) cout<<a[0][i]<<" "; 40 cout<<sortx(1,n,0); 41 42 43 44 return 0; 45 }
原文:https://www.cnblogs.com/adaxyy/p/14771210.html