欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求第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;
}