数组中的第K个最大元素

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

思路：

通过快速排序的思想，每次选取一个基准点，完成划分使得基准点左侧元素都小于等于基准点，右侧元素都大于等于基准点，这一步和快排思路是一样的，都是通过交换。获取基准点的位置后，判断是不是需要的第K大元素，如果该元素比第K大元素大，那就在基准点后面的范围内继续递归搜索，如果该元素比第K大元素小，那就在基准点前面的范围内搜索。
比较重要的一点是选取基准元素时，进行随机选取，可以加速递归的过程。

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

    public int findKthLargest(int[] nums, int left, int right ,int k){
        int index = randomFindPartition(nums, left, right);
        if(index == nums.length-k){
            return nums[index];
        }
        else if(index > nums.length-k){
            return findKthLargest(nums, left, index-1, k);
        }
        else{
           return findKthLargest(nums, index+1, right, k);
        }
    }

    //随机选取一个点，作为基准点，移动交换后返回其索引位置
    public int randomFindPartition(int[] nums, int left ,int right){
        //当left==right时，区间中只有一个数，直接返回
        if(left >= right){return left;}
        int randomIndex = new Random().nextInt(right-left)+left;
        swap(nums, left, randomIndex);
        int i = left;
        int j = right;
        int flag = nums[left];
        while(i<j){
            while(nums[j] >= flag && i<j){j--;}
            while(nums[i] <= flag && i<j){i++;}
            swap(nums, i ,j);
        }
        swap(nums, left, j);
        return j;
    }

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