leetcode 215. 数组中的第K个最大元素（medium）（小林出品必属精品）

代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums,0,nums.length-1,k);
    }

    //查找 nums 数组中，l~r 区间第 k 大的元素
    public int find(int[]nums,int l,int r,int k){
        //递归出口
        if(l>=r){
            return nums[l];
        }
        //随机选择一个基准元素
        int key=nums[new Random().nextInt(r-l+1)+l];
        //根据基准元素将数组划分为 >key =key <key 3个部分
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<key){
                left++;
                swap(nums,i,left);
                i++;
            }else if(nums[i]==key){
                i++;
            }else{
                right--;
                swap(nums,i,right);
            }
        }

        //计算出 3 个区间各自的数据个数
        int a=left-l+1; // <key 区间的数据个数
        int b=right-left-1; // =key 区间的数据个数
        int c=r-right+1;    // >key 区间的个数

        //判断要找的值在哪一个区间，到对应的区间去找
        if(k<=c){
            return find(nums,right,r,k);
        }else if(k<=b+c){
            return key;
        }else{
            return find(nums,l,left,k-b-c);
        }

    }

    public void swap(int[]nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

题解：

? ? ? ? 要找数组中第K个最大元素这种题目通常采用小根堆来解决，但是使用小根堆的时间复杂度为O(NlogN)，所以本题我们采用快速选择的方法来找到数组中的第 K 个最大元素。

? ? ? ? 快速选择方法的核心就是快速排序的核心，要先随机取一个基准数据 key，按照基准数据 key 将数组划分为 3 个区间，分别是 > key , = key ,< key 的区间，根据每个区间的数据个数，判断第 K 个最大元素在哪一个区间，再去该区间用同样的方式寻找数据

? ? ? ? 对于将数组通过基准元素划分为 3 个区间的方法推荐先看leetcode 75. 颜色分类（medium）（优质解法）这里就不进行赘述了，将数组划分以后如下图所示：

? ? ? ? 上图的 a,b,c 分别代表对应区间的数据个数，根据上图标注的下标：

? ? ? ? a = left - l + 1 , b = right - left - 1 , c = r - right + 1?

????????我们要找的是第 K 个最大元素就要先在 > key 这个区间寻找：

????????当 k <= c 时，代表第 K 个最大元素在 > key 的区间，那么我们在区间【right，R】（> key）的区间中继续执行相同的操作去寻找第 K 个最大元素（递归）

? ? ? ? 要是不满足上述条件，说明第 K 个最大元素不在 > key 的区间，判断 k <= b + c,代表第 K 个最大元素在 =?key 的区间，直接返回 key 即可

? ? ? ? 要是不满足上述条件，说明第 K 个最大元素在 < key 区间，此时 = key 和 > key 区间已经有了 b+c 个数据，所以要在< key 区间找到第 k - b - c 大的数据（递归）