题解 | #寻找第K大#

我骄傲了，第一次写题解

总的思想就是，每一次快排后参考值的位置对于完全有序的数组来说就已经确定了，判断参考值位置在目标位置的左边还是右边或者相等。
如果参考值位置在目标位置的左边，说明参考值小于目标值，则需要对参考值右部分进行快排重新获取位置
如果参考值位置在目标位置的右边，说明参考值大于目标值，则需要对参考值左部分进行快排重新获取位置
相等则返回

public class Solution {
    //一次快排后参考值位置就已经确定了，判断这个位置是否等于给定值
    //如果小于则对右边部分快排，大于则对左边部分快排
    public int findKth(int[] a, int n, int K) {
        // write code here
        if(a==null||a.length==0){
            return 0;
        }
        int left = 0;
        int right = n-1;
        //转换一下，第k大的元素索引为n-k
        int target = n-K;
        while(true){
            int index = getIndex(a,left,right);
            if(index == target){
                return a[index];
            }else if(index<target){
                left = index+1;//对右边进行快排
            }else{
                right = index-1;//对左边进行快排
            }
        }
    }
    //快排获取参考值位置
    public int getIndex(int[] arr,int left,int right){
        int i = left,j = right;
        int base = arr[left];//参考值
        while(i<j){
            //从右边开始找，找到第一个小于参考值的数
            while(arr[j]>=base&&i<j){
                j--;
            }
            //从左边开始找，找到第一个大于参考值的数
            while(arr[i]<=base&&i<j){
                i++;
            }
            //找到后交换这两个数
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        arr[j] = base;//参考值的位置就在j处
        return j;
    }
}