求第k小的数 O(n)复杂度

时间：2024-01-09 16:52:38

思路：利用快速排序的思想，把数组递归划分成两部分。设划分为x，数组左边是小于等于x，右边大于x。关键在于寻找一个最优的划分，经过 Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan五位大牛的研究总结，提出了BFPRT 算法（也就是中位数的中位数算法），利用中位数的中位数算法得到的数作为划分可以实现最优划分--在最差情况下能实现O（n）复杂度。接下来考虑可能出现许多重复的数，假设数组中所有的数全部相同，每次划分之后都是当前区间的右端点，即会退化到O（n^2）复杂度。我也是没处理好重复元素，导致TLE多次。一个比较好的办法就是改写partion算法，设每次划分的标准数为x，将所有的与x相等的元素集中到一起，例如数组a[]={4,4,4,2,1,4,5,6},x=4,划分之后应该是{1,2,4,4,4,4,5,6}。很容易能得到等于x的元素的个数cnt，接下来就是决策的处理：

设当前划分的下标为ind.

如果ind+1==k，直接返回a[ind]

如果ind+1<k，递归进入[ind+1,r)的区间继续寻找答案

接下来就是处理重复元素的关键步骤，如果ind+1>k

可分成两种情况：

1、k位于重复元素[ind+1-cnt+1,ind+1]之中，直接返回a[ind]，直接结束程序.

2、k位于所有重复元素之前，则应该丢弃重复元素，递归进入[l,ind-cnt+1)的区间继续寻找答案

当然，这题n<=10^6，直接用sort以O(nlgn)也能过。

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int n,k;
inline int findmid(int l,int r){  //中位数的中位数
	if(r-l<=5) return (l+r)/2;
	for(int i=0;i<(r-l)/5;++i){
		sort(a+l+i*5,a+l+i*5+5);
		swap(a[l+i],a[l+i*5+2]);
	}
	return findmid(l,l+(r-l)/5);
}
int partion(int l,int r,int &p){ //改进版partion
	int h=findmid(l,r);
	swap(a[h],a[r-1]);
	p=0;
	int ind=l-1;
	for(int i=l;i<r-1;++i){
		if(a[i]==a[r-1]) ++p;
		if(a[i]<=a[r-1])
			swap(a[++ind],a[i]);
	}
	++p;
	swap(a[++ind],a[r-1]);
	int i=l,j=ind-1;
	while(i<j){
		if(a[i]==a[ind]){
			while(a[j]==a[ind]) --j;
			if(i<j){
				swap(a[i],a[j]);
				--j;
			}
		}
		++i;
	}
	return ind;
}
int solve(int l,int r){
	int p=0;
	int ind=partion(l,r,p);
	if(ind+1==k) return a[ind];
	if(ind+1>k){
		if(ind+1-p+1<=k) return a[ind];
		else return solve(l,ind-p+1);
	}
	if(ind+1<k) return solve(ind+1,r);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;++i) scanf("%d",&a[i]);
	printf("%d\n",solve(0,n));
	return 0;
}

如有不当之处欢迎指出！

相关文章