一、相关概念

二、题目

题目

一个未排序的数组中找第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);
        }
            
    }
}

参考文献

数组中的第K个最大元素