题解 | #寻找第K大#

// 非常厉害的一道题，看懂了直呼斯巴拉西
// 妙啊，看我写的这些注释就懂了
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here
        // 快排思路
        return partition(0,n-1,a,K);

    }
    // 交换函数，常用
    public void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    // 实现快排，标杆元素坐便大于它，右边小于它
    public int partition(int left,int right,int[] arr,int k){
        Random r = new Random();
        int i = left+1;//1
        int j = right;//n-1
        int flag = Math.abs(r.nextInt()) % (right-left+1) + left;//标杆索引
        swap(arr,flag,left);// 如下
        // 标杆元素移到索引0位置，左边从1，右边从n-1，依次遍历比较与交换
        // 直到左右索引交叉，此后再判断第k与j的关系
        while(true){
            // 上面交换后，索引left处即标杆元素
            // 小于标杆，元素不动，索引动
            while(j>=left+1 && arr[j] < arr[left])  j--;
            while(i<=right && arr[i] > arr[left])  i++;
            // 经过上面的循环遍历，当前i和j索引位置需要交换一次之后更新索引
            if(i > j)  break;//交叉了，在交换元素之前，必须跳出循环
            swap(arr,i,j);
            i++;
            j--;
        }
        // 以上实现了快排
        // 交换标杆元素和大于它的最后一个元素
        swap(arr,left,j);
        // 索引j刚好为第k个，而前面都是比它大的
        if(j+1 == k)    return arr[j];
        // 左边继续找
        else if(j+1 > k)   return partition(left,j-1,arr,k);
        else   return partition(j+1,right,arr,k);
      
    }
}