基于快速排序的选择方法

public class Solution {
    private int quickSelect(List<Integer> nums, int k) {
        // 随机选择基准数
        Random rand = new Random();
        int pivot = nums.get(rand.nextInt(nums.size()));
        // 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (int num : nums) {
            if (num > pivot)
                big.add(num);
            else if (num < pivot)
                small.add(num);
            else
                equal.add(num);
        }
        // 第 k 大元素在 big 中，递归划分
        if (k <= big.size())
            return quickSelect(big, k);
        // 第 k 大元素在 small 中，递归划分
        if (nums.size() - small.size() < k)
            return quickSelect(small, k - nums.size() + small.size());
        // 第 k 大元素在 equal 中，直接返回 pivot
        return pivot;
    }
    
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numList = new ArrayList<>();
        for (int num : nums) {
            numList.add(num);
        }
        return quickSelect(numList, k);
    }
}

要点

• 随机选择基准数
• 判断第 k 大元素在哪个数组中，如何循环
• 如何将 int[] nums 转换为 List<Integer> numList，除了循环有没有别的方式？（可以使用 Stream，或者不要考虑那么多，直接使用循环）

<aside> 💡 第 n 次写这道题，不要眼高手低啊，多练习（还好写出来了）

</aside>

基于堆排序的选择方法

<aside> ⏰ 下回再写的时候记得把堆排序看一下

</aside>