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

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 小顶堆：始终维护“当前扫描过的元素里最大的 k 个数”
        // 堆顶（最小值）就是这 k 个数里最小的那个，也就是当前第 k 大
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 遍历数组中的每个元素，动态维护前 k 大候选集
        for (int num : nums) {
            // 边界情况1：堆中元素不足 k 个时，直接放入堆中补满候选集
            if (minHeap.size() < k) {
                minHeap.offer(num);
            // 堆已满时，只有当当前元素比堆顶更大，才有资格进入“前 k 大”
            } else if (num > minHeap.peek()) {
                // 先移除当前候选集中最小的元素（也就是堆顶）
                minHeap.poll();
                // 再把更大的新元素加入候选集
                minHeap.offer(num);
            }
            // 如果 num <= 堆顶，说明它不可能进入前 k 大，直接忽略
        }

        // 遍历结束后，堆顶就是第 k 大元素
        return minHeap.peek();
    }
}

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大 => 升序数组中的下标 nums.length - k
        int target = nums.length - k;
        // 当前在 [left, right] 区间内做快速选择
        int left = 0;
        int right = nums.length - 1;

        // 只要区间有效，就不断做 partition 缩小搜索范围
        while (left <= right) {
            // 以 nums[right] 为基准值做一轮划分，返回基准值最终落点
            int pivotIndex = partition(nums, left, right);
            // 命中目标下标，直接返回答案
            if (pivotIndex == target) {
                return nums[pivotIndex];
            // 基准位置偏左，说明目标在右半区
            } else if (pivotIndex < target) {
                left = pivotIndex + 1;
            // 基准位置偏右，说明目标在左半区
            } else {
                right = pivotIndex - 1;
            }
        }

        // 理论上不会走到这里（题目保证 k 合法），仅作为兜底返回
        return -1;
    }

    private int partition(int[] nums, int left, int right) {
        // 选择最右侧元素作为基准值
        int pivot = nums[right];
        // smallerIndex 指向“下一个应放置小于 pivot 元素”的位置
        int smallerIndex = left;

        // 遍历 [left, right - 1]，把小于 pivot 的元素都交换到前面
        for (int index = left; index < right; index++) {
            // 当前元素小于基准值，放到左侧“小元素区”
            if (nums[index] < pivot) {
                swap(nums, smallerIndex, index);
                // 小元素区边界右移一位
                smallerIndex++;
            }
        }

        // 最后把基准值放到小元素区之后，完成最终落位
        swap(nums, smallerIndex, right);
        // 返回基准值的最终下标，用于下一轮二分式缩小区间
        return smallerIndex;
    }

    private void swap(int[] nums, int first, int second) {
        // 临时变量保存第一个位置的值
        int temp = nums[first];
        // 把 second 位置的值放到 first
        nums[first] = nums[second];
        // 把原 first 的值放到 second，完成交换
        nums[second] = temp;
    }
}