/**
* 查找一个无序数组中 第K大的元素
* 这里我们可以使用快排 分区 分治的思想去解决
* <p>
* 先按分区点 分区，然后判断分区点的值 是大于还是小于第K大元素，然后再递归接着处理，直接找到值
*/
public class findK {
public static void main(String[] args) {
int[] array = {6, 3, 4, 8, 1, 6};
System.out.println(findK(array, 2, 0, array.length - 1));
}
private static int findK(int[] array, int k, int start, int end) {
if (k > end + 1 || k < 0) return -1;
if (start >= end) return array[start];
int index = findPortionIndex(array, start, end);
if (index + 1 == k) return array[index];
else if (index + 1 > k) return findK(array, k, start, index - 1);
else return findK(array, k, index + 1, end);
}
/**
* 获取分区点的下标值, 同时对数据源进行分区
*/
private static int findPortionIndex(int[] array, int start, int end) {
int index = start;
int point = array[end];
for (int i = start; i <= end; i++) {
//这里我们只把大于分区点的元素 移动到前面
if (array[i] > point) {
int tmpValue = array[i];
array[i] = array[index];
array[index] = tmpValue;
index++;
}
}
//因为前面的比较 是大于分区点的， 所以在最后的时候，需要把分区点放到 所有小于它的值的前面，
//这里我们只需要把 把分区点和第一个比它小的值 交换一下就可以了，避免了数据的迁移，这里我个人觉得是很精髓的，大大减小了数据迁移的工作量.
array[end] = array[index];
array[index] = point;
return index;
}
}
查找第K大的元素
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 归并排序（分治） 代码实现 性能分析 是稳定算法吗 是稳定算法 时间复杂度 最好、最坏、平均时间复杂度都是O(nl...
- 在大规模数据处理中，经常会遇到的一类问题：在海量数据中找出出现频率最高的前k个数，或者从海量数据中找出最大的...
- 一、分治思想 1.分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大...
