概述
目录
- 问题
- 解析
- 设计
- 分析
- 源码
问题
设 L 是 n 个元素的集合，从 L 中选取第 k 小的元素，其中1<=k<=n。这里的第 k 小元素是指，当 L 按从小到大排好序之后，排在第 k 个位置的元素。
解析
使用特定分治策略选择第k小元素的核心是将原问题通过五元分组排序划分为两个子问题，并不断减小问题规模直至找出答案。
设计
算法核心伪代码：
void select(Integer[] a, int n, int k){
// 将a划分为 ⌈ |a| /5 ⌉ 组
// 排序选出每组中位数中的中位数m*
// 每组中位数和m*比较，将组内元素划分到较小组s1和较大组s2中
if(k==s1.size()){
// 结果为m*
return;
}else if(k<=s1.size()){
select(s1, s1.size(), k);
}else{
select(s2, s2.size(), k-s1.size()-1);
}
}
分析
时间复杂度：W(n)=O(n)
源码
GitHub
最后
以上就是奋斗高跟鞋为你收集整理的选第k小元素：特定分治策略问题解析设计分析源码的全部内容，希望文章能够帮你解决选第k小元素：特定分治策略问题解析设计分析源码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复