题解 | #寻找第K大#

使用快排的思想，因为快速排序每次确定一个数的位置，我们将数组从大到小排序，每次判断当前排好序的数的位置low是否==K,如果等于的话当前数就是第K大的数，否则如果比K小则对它的右半部分进行快排，如果比K大对它的左半部分进行快排

import java.util.*;

public class Solution {
    int res;
    public int findKth(int[] a, int n, int K) {
        if(n<1 || K>n)
            return -1;
        // write code here
        quickSort(a,0,n-1,K);
        return res;
    }
    // 逆序 从大到小 快排每次确定一个数的位置
    private void quickSort(int[] a,int l,int r,int k){
        int low = l;
        int high = r;
        int base = a[low];
        while(low < high){
            // mid 右边是 <= base的
            while(low<high && base >= a[high])
                high--;
            a[low] = a[high];
            // mid左边是 > base的
            while(low<high && base < a[low])
                low++;
            a[high] = a[low];
        }
        // low左边是大于base的  右边是小于等于base的
        a[low] = base;
        if((low+1) == k){
            res = base;
            return;
        //low 是第low+1 大的数 如果low小于k 说明第k大的数在low右边
        }else if((low+1)<k){
            quickSort(a,low+1,r,k);
        }else{
            quickSort(a,l,low-1,k);
        }

    }
}