数组中的第K个最大元素

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

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

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

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

思路：

https://www.bilibili.com/video/BV1hTfBBuE4T/?spm_id_from=333.337.search-card.all.click&vd_source=499c257f0104fdb6ce035bd58aedbdf9

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    private Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        // 为了方便后续的递归操作，先将基本类型数组转换为 List
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        return quickSelect(list, k);
    }
    
    private int quickSelect(List<Integer> nums, int k) {
        // 取一个随机数为标记
        int pivot = nums.get(random.nextInt(nums.size()));
    
        // 分成左，中，右三块区域
        List<Integer> left = new ArrayList<>();
        List<Integer> mid = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
    
        for (int x : nums) {
            if (x > pivot) {
                left.add(x);   // 放比基准大的数 (因为要找第 K 大)
            } else if (x == pivot) {
                mid.add(x);    // 放等于基准的数
            } else {
                right.add(x);  // 放比基准小的数
            }
        }
    
       
        if (k <= left.size()) {
            return quickSelect(left, k);
        } else if (k <= left.size() + mid.size()) {
            return pivot;
        } else {
            return quickSelect(right, k - left.size() - mid.size());
        }
    }

}