题目来源：

题目来源

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解析

使用快速排序法

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

    public static int findK(int[] nums, int l, int r, int k, Random random) {
        int p = partition(nums, l, r, random);
        if (k == p) return nums[p];
        if (k < p) {
            return findK(nums, l, p - 1, k, random);
        }
        return findK(nums, p + 1, r, k, random);
    }

    private static <E extends Comparable<E>> int partition(int[] arr, int l, int r, Random random) {
        int p = l + random.nextInt(r - l + 1);
        swap(arr, l, p);
        int i = l + 1, j = r;
        // 第一步，将获得的随机值挪到最左边
        while (true) {
            while (i <= j && arr[i] < arr[l]) {
                i++;
            }
            while (j >= i && arr[j] > arr[l]) {
                j--;
            }
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


}