求第K小的数(分治)
程序员文章站
2022-05-12 10:57:50
...
利用快排思想,每次以第一个数为基准,将小于它的数放到左边,大于它的数放到右边,调整后,判断该数的位置与K的关系,从而只需要继续查找某一边的子数组,通过分治降低了问题规模,也降低了时间复杂度。
//时间复杂度O(n)
#include<bits/stdc++.h>
#define N 10000000
using namespace std;
int n,k,ans,a[N];
void search(int l,int r,int k){
if(l>r) return;
int x=a[l];
int i=l,j=r;
while(i<j){
while(a[j]>=x&&i<j){
j--;
}
a[i]=a[j];
while(a[i]<=x&&i<j){
i++;
}
a[j]=a[i];
}
a[i]=x;
if(i==k){
ans=x;
return;
}
else if(i<k){//划分的数的位置小于K,答案在右半部分
search(i+1,r,k);
}
else{
search(l,i-1,k);//划分的数的位置大于K,答案在左半部分
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
search(1,n,k);
printf("%d",ans);
return 0;
}