贪心与堆中等2 种解法

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

在未排序数组中返回按降序排列后的第 k 个元素，而不是第 k 个不同元素。

#数组#快速选择#堆#分治

解题主线

容量为 k 的小根堆保存当前最大的 k 个值，堆顶就是这些值中最小的，也就是最终第 k 大。

第 k 大对应升序下标 n - k；快速选择每次分区后只进入包含该下标的一侧。

随机枢轴降低有序或刻意构造输入持续产生极端分区的概率。

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

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

时间复杂度

O(n log k)

空间复杂度

O(k)

215. 数组中的第 K 个最大元素 · 容量为 k 的小根堆

java

import java.util.PriorityQueue;

final class Solution {
    public int findKthLargest(int[] nums, int 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();
    }
}

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

解法 2：随机化快速选择

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

时间复杂度

期望 O(n)，最坏 O(n²)

空间复杂度

O(1)

215. 数组中的第 K 个最大元素 · 随机化快速选择

java

import java.util.concurrent.ThreadLocalRandom;

final class Solution {
    public int findKthLargest(int[] nums, int 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;
    }
}

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

边界与易错点

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

整理来源

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

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