215.数组中的第k的最大元素 #

int findKthLargest(int[] nums, int k) {
    // 小顶堆，堆顶是最小元素
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int e : nums) {
        // 每个元素都要过一遍二叉堆
        pq.offer(e);
        // 堆中元素多于 k 个时，删除堆顶元素
        if (pq.size() > k) {
            pq.poll();
        }
    }
    // pq 中剩下的是 nums 中 k 个最大元素，
    // 堆顶是最小的那个，即第 k 个最大元素
    return pq.peek();
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 随机打乱数组
        shuffle(nums);
        int l = 0, r = nums.length - 1;
        int t =  nums.length - k;
        while(l <= r){
            // 进行一轮快速排序，排序后返回的位置就是该元素正确的位置，再根据需求，继续排序下一个点
            int p = partition(nums, l, r);
            if(p < t){
                l = p + 1;
            }else if(p > t){
                r = p - 1;
            }else{
                return nums[p];
            }
        }
        return -1;
    }
    // 快速排序核心逻辑
    public int partition(int[] nums, int lo, int hi){
        if(lo == hi) return lo;
        int l =  lo,r = hi + 1;
        // 取第一个值为目标值
        int pivot = nums[lo];
        while(true){
            // 从下一位开始比较大小，直到比目标值大
            while(nums[++l] < pivot){
                if(l == hi) break;
            }
            // 从最后一位开始比较大小，直到比目标值小
            while(nums[--r] > pivot){
                if(r == lo) break;
            }
            // 如果判断到同个位置
            if(l >= r) break;
            // 交换两个位置的值，继续下一轮
            swap(nums, l, r);
        }
        // 将目标值放在正确的位置
        swap(nums,r,lo);
        // 返回位置
        return r;
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    // 对数组元素进行随机打乱
    public void shuffle(int[] nums) {
        int n = nums.length;
        Random rand = new Random();
        for (int i = 0 ; i < n; i++) {
            // 从 i 到最后随机选一个元素
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }
}