分治策略找第K小元素
1.问题
使用特定的分治策略去寻找无序数组中第 k小的元素。
2.分析
以此递归，直到剩余最后一个数，那个数就是第k小的数
3.算法
int Select(int a[],int l,int r,int k){
if (l==r) return a[l];
int i=l,j=r;
int x = a[i];
while(i<j){
while(i<j && a[j]>=x) j--;
a[i]=a[j];
while (i<j && a[i]<=x)i++;
a[j] = a[i];
}
a[i]=x;
int num =i-l+1;
if(num<k) return Select(a,i+1,r,k-num);
return Select(a,l,i,k);
}
4.分析
时间复杂度为O(n)
源码：https://github.com/Ace16602/-3/commit/8fe60146d60aa4bb4b62b2ba0ea0e8af7cfc6096
最后
以上就是欢喜墨镜最近收集整理的关于分治策略找第K小元素分治策略找第K小元素的全部内容，更多相关分治策略找第K小元素分治策略找第K小元素内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复