题解 | #寻找第K大#

public class Solution {
    
    /*
    1.第1大的数最大
    2.第k大的数是从大到小排序后的第k个数
    3.从大到小排序,排完一次,枢纽左边的数比枢纽大,右边的比枢纽小,枢纽的index + 1 代表枢纽是第几大的数
    */
    public int findKth(int[] a, int n, int K) {
        // write code here
        return quickSort(a,0,n-1,K);
        
    }
    
    public int quickSort(int[] a,int left, int right, int k){
        if(left < right){
            int i = left;
            int j = right;
            int temp = a[i];
            
            while(i < j){
                while(i < j && a[j] <= temp){
                    j--;
                }
                if(i < j){
                    a[i++] = a[j];
                }

                while(i < j && a[i] >= temp){
                    i++;
                }
                if(i < j){
                    a[j--] = a[i];
                }
            }
            
            a[i] = temp;
            // 判断 枢纽是不是第k大的数
            if(i + 1 == k){
                return temp;
            }else if(i + 1 > k){ //第k大的数在枢纽的右边
                return quickSort(a,left,i-1,k);
            }else { // 第k大的数在枢纽的左边
                return quickSort(a,i+1,right,k);
            }
        }else{
            return a[left];
        }
    }
}