一、相关概念
二、题目
题目
一个未排序的数组中找第k大的数
思路
快排
代码
/**
* [3,2,1,5,6,4] and k = 2——>Output:2
* <p>Description: </p>
* @author 杨丽金
* @date 2018-9-16
* @version 1.0
*/
public class 求第K个大的数 {
public static void main(String[] args) {
int[] arr={2,1};
int r=f(arr,0,arr.length-1,2);
System.out.println(r);
}
// 求数组[l,h]范围内的第k大的数，编号从0开始
public static int f(int[] arr,int l,int h,int k){
if(l>h){
return -1;
}
int i=l,j=h;
// 基准
int temp=arr[l];
while(i<j){
while(arr[j]>temp && i<j){
j--;
}
if(i<j){
arr[i]=arr[j];
i++;
}
while(arr[i]<temp && i<j){
i++;
}
if(i<j){
arr[j]=arr[i];
j--;
}
}
arr[i]=temp;
// // 第k大就是排序后在数组中最终位置时n-1的元素
if(i==arr.length-k){
return arr[i];
}else if(arr.length-k<i){
return f(arr,l,i-1,k);
}else{
return f(arr,i+1,h,k);
}
}
}
