LeetCode215. 数组中的第K个最大元素

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

分析：
本题我们能想到最简单的方法就是直接给数组排序，然后取第第N-k个元素，但题目要求是O(n)的时间复杂度，这是不论哪种排序方法都无法做到的，所以我们肯定要进行优化。

我们可以基于排序的这种思想进行拓展，快速排序的思想是找一个随机值，将小于它的放到左边，大于它的放到右边。但是如果数组中有很多重复元素的话会多次将数据分成长度为1和n-1，使得时间复杂度变成了$n^2$，因此我们的快速选择算法就是基于他改变出来的，我们可以将数组分成三个部分，大于的，小于的，等于的，这样就不会出现上面的问题了。然后根据这三个集合的大小判断我们要找的第k个最大的元素在哪个集合中，进行递归解决

源代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        List numsList = new ArrayList<Integer>();
        for(int num:nums) numsList.add(num);
        int num = quickSelect(numsList, k);
        return num;
    }

    public int quickSelect(List<Integer> nums, int k){
        // 随机选取一个数作为基准数
        Random random = new Random();
        int p = nums.get(random.nextInt(100010)%nums.size());
        List<Integer> big = new ArrayList<Integer>();
        List<Integer> equals = new ArrayList<Integer>();
        List<Integer> small = new ArrayList<Integer>();
        for(int num : nums){
            if(num > p) big.add(num);
            else if(num == p) equals.add(num);
            else small.add(num);
        }

        // 第k大的元素在big集合中
        if(big.size() >= k) return quickSelect(big, k);
        // 第k大的元素在small集合中
        if(big.size() + equals.size() < k) return quickSelect(small, k - big.size() - equals.size());
        // 第k大的元素在equals集合中
        return p;
    }
}

本题到这里就结束了，在做到这个题的时候是没什么思路的，也没有看到能讲的比较清楚的文章。在看完官方的解答和评论区后恍然大悟，想着分享一下。