题解 | 寻找第K大

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    Random random =new Random();
    public int findKth (int[] a, int n, int k) {
        // write code here
        int left=0,right=n-1;
        while(left<=right){
            int mid=divide(a,left,right);
            if(mid==(n-k))return a[mid];
            else if(mid<n-k)left=mid+1;
            else right=mid-1;
        }
        return -1;
    }
    public int divide(int[]arr,int left,int right){
        swap(arr,left,left+random.nextInt(right-left+1));
        int pv=arr[left];
        int l=left+1;
        int r=right;
        while(true){
            while(l<=r&&arr[l]<pv)l++;
            while(l<=r&&arr[r]>pv)r--;
            if(l>r)break;
            swap(arr,l,r);
            l++;
            r--;
        }
        swap(arr,r,left);
        return r;
    }
    public void swap(int[]arr,int left,int right){
        int t=arr[left];
        arr[left]=arr[right];
        arr[right]=t;
    }
}
快速排序分区不均匀的情况下时间复杂度是n*n

一、选择随机pv值的目的是避免在数组已经有序的情况下分区不均匀：1，2，3，4，5，6，7，8，9如果每次选择left作为pv值，那么分区情况：
2，3，4，5，6，7，8，9和null
3，4，5，6，7，8，9和null
4，5，6，7，8，9和null
。。。。。。。
时间复杂度退化为n*n
所以我们需要  swap(arr,left,left+random.nextInt(right-left+1));




二、选择双边循环快排而不是单边循环，目的是避免pv值出现大量重复的情况下分区不均匀，比如全是1的数组：
1，1，1，1，1，1，1，1，1
如果选择单边循环快排,要么都交换（全部分在左边），要么都不交换（全部分在右边），无论哪种，都会导致分区不均匀
代码类似于：
private static int partition(int[] arr, int low, int high) {
        // 选择最后一个元素作为基准
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            // 当前元素小于等于基准时，交换到 i 的位置
            if (arr[j] <= pivot) {
                swap(arr, i++, j);
            }
        }
        // 将基准放到正确的位置
        swap(arr, i , high);
        return i ;
    }
其中arr[j] <= pivot对应都交换的情况，arr[j] < pivot对应都不交换的情况

而双边循环快排很好的避免了分区不均匀，左右指针指向和pv相同的元素的时候都会直接停下，然后交换左右指针的元素，最后左指针加一右指针减一：
while(true){
            while(l<=r&&arr[l]<pv)l++;
            while(l<=r&&arr[r]>pv)r--;
            if(l>r)break;
            swap(arr,l,r);
            l++;
            r--;
        }
可以看到如果arr[l]==pv或者arr[r]==pv那么while循环会退出，最后l++，r--
 对于全是相同元素的数组：1，1，1，1，1，1，1，1，1依然能够实现均匀分区，避免时间复杂度退化为n*n
 
 分区函数写好了剩下的就简单了