首页 > 代码库 > 【算法导论学习-015】数组中选择第i小元素（Selection in expected linear time）
【算法导论学习-015】数组中选择第i小元素（Selection in expected linear time）
1、算法思想
问题描述：从数组array中找出第i小的元素（要求array中没有重复元素的情况），这是个经典的“线性时间选择（Selection in expected linear time）”问题。
思路：算法导论215页9.2 Selection in expect linear time
2、java实现
思路：算法导论216页伪代码
/*期望为线性时间的选择算法，输入要求，array中没有重复的元素*/
public static int randomizedSelect(int[] array,int start,int end,int i) {
if (start==end) {
return array[start];
}
int middle=randomizedPartition(array, start, end);
int k=middle-start+1;
if (i==k) {
return array[middle];
}else if (i<k) {
return randomizedSelect(array, start, middle-1, i);
}else {
return randomizedSelect(array, middle+1, end, i-k);
}
}
randomizedPartition(array,start,end)参见：【算法导论-010】快速排序（quickSort）3、非递归版本
/*非递归版本的线性时间选择*/
public static int iterativeRandomizedSelect(int[] array,int start,int end,int i) {
int result=0;
while (start<=end) {
if (start==end) {
return array[start];
}
int middle=randomizedPartition(array, start, end);
int k=middle-start+1;
if (i==k) {
result= array[i];
} else if (i<k) {
end=middle-1;
}else {
start=middle+1;
i=i-k;
}
}
return result;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。