当前位置: 首页 > >

寻找数组中第k大的数

发布时间:

题目:有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。


给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。


测试样例:
[1,3,5,2,2],5,3

返回:
2

?


方法一:

利用冒泡排序,进行k趟排序,即可查找到第k大的数(每趟冒泡排序都寻找当前序列中的最大值)


方法二:

利用选择排序,进行k趟排序,即可查找到第k大的数(每趟选择排序都寻找当前序列中的最大值)


方法三:

利用快速排序的思想,只需找到第k大的数,不必把所有的数排好序。


思路分析:先任取一个数(找到基准值),把比它大的数移动到它的右边,比它小的数移动到它的左边。移动完成一轮后,看该数的下标(从0计数),如果刚好为length-k,则它就是第k大的数(因为移动后的基准值左边都是比它小的数,右边都是比他大的数,右边若没有元素,则说明当前基准值是第1大元素,若右边有1个元素,则说明当前基准值是第2大元素,若右边有2个元素,则说明当前基准值是第3大元素......即当前基准值右边有k-1个元素,或当前基准值的下标为length-k,则说明当前基准值是第k大元素),如果小于length-k,说明第k大的数在它右边,如果大于length-k,则说明第k大的数在它左边,取左边或者右边继续进行移动,直到找到。


代码实现:


package com.csu.marden;

public class Demo6 {
public static void main(String[] args) {
int [] arr={3,1,2,5,4,7,6};
int k=2;
System.out.println(quickSort(arr, 0, arr.length-1, k));

}


//使用快速排序的原理,寻找第k大的数
public static int quickSort(int [] arr,int start,int end,int k){
//递归结束条件
if(start>end){
return -1;
}
int i=start;
int j=end;
int base=arr[start];
while(i while(i=base){
j--;
}
while(i i++;
}
if(i int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
//此时i=j,交换base元素的位置
arr[start]=arr[i];
arr[i]=base;
if(i==arr.length-k){
//查找到第k大的数字
return arr[i];
}
else if(i //在基准值右边寻找
return quickSort(arr, i+1, end, k);
}else{
//在基准值左边寻找
return quickSort(arr, start, i-1, k);
}
}

}

方法四:

针对海量数据,数据量太大无法加载到内存,若采用上述方法,必须将所有数据加载到内存进行排序,尤其是快速排序,使用递归需要额外的空间开销,此时可以使用堆排序,利用较少的空间即可找到第k大的数。


思路分析:


寻找第k大的数,可以在内存中构建一个包含k个数的小顶堆(堆顶元素是最小值),然后从外存中第k+1个数据开始,依次与小顶堆的堆顶元素进行比较,若该数比堆顶元素大,则用该数替换堆顶元素,并重新构建小顶堆,重复上述操作,直到外存中的所有数据遍历完成,此时小顶堆的堆顶元素即为第k大的数。


?


?



友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网