贪心与堆中等2 种解法

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

在未排序数组中返回按降序排列后的第 k 个元素，而不是第 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

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

查看原题

解题主线

容量为 k 的小根堆保存当前最大的 k 个值，堆顶就是这些值中最小的，也就是最终第 k 大。
第 k 大对应升序下标 n - k；快速选择每次分区后只进入包含该下标的一侧。
随机枢轴降低有序或刻意构造输入持续产生极端分区的概率。

解法 1：容量为 k 的小根堆

先把前 k 个元素入堆，之后仅当新值大于堆顶时替换堆顶；扫描结束后堆顶即第 k 大。

时间复杂度： O(n log k)
空间复杂度： O(k)

JAVA

import java.util.PriorityQueue;

final class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大等价于升序下标 n-k，只需保留或定位这一排名。
        // 参数校验必须先于数组访问，避免非法 k 破坏排名不变量。
        if (nums == null || k < 1 || k > nums.length) {
            throw new IllegalArgumentException("k must be in [1, nums.length]");
        }

        PriorityQueue<Integer> largest = new PriorityQueue<>(k);
        for (int value : nums) {
            if (largest.size() < k) {
                largest.offer(value);
            } else if (value > largest.peek()) {
                largest.poll();
                largest.offer(value);
            }
        }
        return largest.peek();
    }
}

解法 2：随机化快速选择

使用随机枢轴做 Lomuto 分区，比较枢轴最终位置与目标下标，只在目标所在一侧继续迭代。

时间复杂度： 期望 O(n)，最坏 O(n²)
空间复杂度： O(1)

JAVA

import java.util.concurrent.ThreadLocalRandom;

final class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大等价于升序下标 n-k，只需保留或定位这一排名。
        // 参数校验必须先于数组访问，避免非法 k 破坏排名不变量。
        if (nums == null || k < 1 || k > nums.length) {
            throw new IllegalArgumentException("k must be in [1, nums.length]");
        }

        int target = nums.length - k;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == target) return nums[pivotIndex];
            if (pivotIndex < target) left = pivotIndex + 1;
            else right = pivotIndex - 1;
        }
        throw new IllegalStateException("unreachable");
    }

    private int partition(int[] nums, int left, int right) {
        int randomIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
        swap(nums, randomIndex, right);
        int boundary = left;
        for (int i = left; i < right; i++) {
            if (nums[i] <= nums[right]) {
                swap(nums, boundary++, i);
            }
        }
        swap(nums, boundary, right);
        return boundary;
    }

    private void swap(int[] nums, int first, int second) {
        int temporary = nums[first];
        nums[first] = nums[second];
        nums[second] = temporary;
    }
}

边界与易错点

k 的合法范围是 [1, nums.length]。
快速选择会原地改写数组；若调用方要保留输入，应先复制。
旧文件两种快速选择、两种小根堆分别只是分区或堆实现细节差异；整理后按算法策略去重为两解法。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q215_findKthLargest.java