LeetCode 215. 数组中的第K个最大元素——快速选择O(n)与堆O(nlogk)

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约22分钟 | 难度：中等

---

开篇故事

这道题是我面试里被考得最多的排序/选择题，没有之一。几乎每一家公司都会考「第K大元素」，区别只在于是链表还是数组，是精确第K大还是前K大。

这道题真正的考察点有两个层次：

1. 能不能写出 O(n log k) 的堆解法（很多人止步于此）
2. 能不能进一步想到 O(n) 均摊的快速选择（真正的优雅）

今天把两种解法都讲透，包括快速选择里的随机化优化，让你在面试中真正拿满分。

---

一、题目解析

题目描述：

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

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

示例：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4

约束：

• 1 <= k <= nums.length <= 10^5

---

二、解法一：全排序

思路分析

排序后直接取第 k 大元素（倒数第 k 个）。

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

复杂度分析

• 时间复杂度：O(n log n)。
• 空间复杂度：O(1) 或 O(log n)（Arrays.sort 使用双轴快排）。

---

三、解法二：最小堆维护前K大

思路分析

维护一个大小为 k 的最小堆。遍历数组：

• 如果堆大小 < k，直接入堆
• 如果当前元素 > 堆顶（最小值），弹出堆顶，入堆当前元素

最终堆顶就是第 k 大的元素。

这个思路特别适合数据流场景（不知道总数量时实时维护前K大）。

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最小堆，维护当前最大的 k 个元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // 弹出最小的，保持堆大小为 k
            }
        }
        
        return minHeap.peek(); // 堆顶是第 k 大的
    }
}

复杂度分析

• 时间复杂度：O(n log k)。每次操作 O(log k)，共 n 次。
• 空间复杂度：O(k)。

---

四、解法三（最优）：快速选择

核心思想

快速选择（QuickSelect）是快速排序的变体。快速排序每次 partition 后，基准元素会到达它最终排好序的位置。如果这个位置恰好是我们要找的位置，就直接返回；否则只在一侧递归。

关键点： 平均情况下，每次 partition 都能把问题规模减半，所以均摊时间复杂度是 O(n)。

随机化： 为避免最坏情况（已排序数组），每次随机选取 pivot，使最坏情况概率极低。

完整代码

import java.util.*;

class Solution {
    private Random random = new Random();
    
    public int findKthLargest(int[] nums, int k) {
        // 第 k 大 = 排序后第 (n-k) 小（0-indexed）
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    /**
     * 找到排序后第 targetIdx 小的元素（0-indexed）
     */
    private int quickSelect(int[] nums, int left, int right, int targetIdx) {
        if (left == right) return nums[left];
        
        // 随机选 pivot，避免最坏情况
        int pivotIdx = left + random.nextInt(right - left + 1);
        swap(nums, pivotIdx, right); // 把 pivot 放到末尾
        
        // partition
        int pivotVal = nums[right];
        int storeIdx = left;
        
        for (int i = left; i < right; i++) {
            if (nums[i] <= pivotVal) {
                swap(nums, i, storeIdx);
                storeIdx++;
            }
        }
        swap(nums, storeIdx, right); // pivot 放到最终位置
        
        if (storeIdx == targetIdx) {
            return nums[storeIdx];
        } else if (storeIdx < targetIdx) {
            return quickSelect(nums, storeIdx + 1, right, targetIdx);
        } else {
            return quickSelect(nums, left, storeIdx - 1, targetIdx);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

三种元素分区的 partition（荷兰国旗）

当数组有大量重复元素时，普通的 partition 效率低。三路 partition（荷兰国旗问题）能显著提升：

// 三路 partition：< pivot | == pivot | > pivot
private int[] threeWayPartition(int[] nums, int left, int right, int pivotVal) {
    int lt = left, gt = right, i = left;
    while (i <= gt) {
        if (nums[i] < pivotVal) {
            swap(nums, lt++, i++);
        } else if (nums[i] > pivotVal) {
            swap(nums, i, gt--);
        } else {
            i++;
        }
    }
    return new int[]{lt, gt}; // [lt, gt] 都等于 pivotVal
}

复杂度分析

• 时间复杂度：均摊 O(n)。T(n) = T(n/2) + O(n) → O(n)。最坏 O(n²)（无随机化时）。
• 空间复杂度：O(log n)。递归栈深度。

堆 vs 快速选择的工程选择

场景	推荐方法	原因
批量静态数组	快速选择	O(n) 更快，空间 O(1)
数据流/在线处理	堆	支持动态插入
k 很小	堆	O(n log k) 当 k << n 时接近 O(n)
对象数组（移动代价高）	堆	避免大量交换

---

五、举一反三

快速选择的变体：

题目	变体
215. 第K大元素	本题
347. 前K个高频元素	桶排序 or 堆
973. 最接近原点的K个点	对距离做快速选择
1991. 找到数组的中间位置	第(n+1)/2小

---

六、踩坑实录

坑一：第K大和第K小的下标转换

第 k 大 = 排序后下标 n-k（0-indexed）。这个转换容易出错，建议写代码时注释说明清楚。

// 第k大 = 排序后第(n-k)小（下标n-k，0-indexed）
return quickSelect(nums, 0, nums.length - 1, nums.length - k);

坑二：不加随机化会被特殊用例卡掉

LeetCode 的测试用例里有专门针对「有序数组+无随机化」的快速排序杀手用例。如果不加随机化，选固定 pivot（如最左或最右），会退化到 O(n²)。

一定要加随机化：

int pivotIdx = left + random.nextInt(right - left + 1);

坑三：堆解法中弹出时机

两种写法都正确，选哪种取决于习惯：

// 写法一：先入后判断
minHeap.offer(num);
if (minHeap.size() > k) minHeap.poll();

// 写法二：先判断
if (minHeap.size() == k && num > minHeap.peek()) {
    minHeap.poll();
    minHeap.offer(num);
} else if (minHeap.size() < k) {
    minHeap.offer(num);
}

写法一更简洁，推荐。

---

七、总结

215 是 TopK 问题的基础题，两种核心解法各有千秋：

• 堆解法 O(n log k)：适合在线/数据流场景，代码简洁稳定
• 快速选择 O(n) 均摊：适合静态批量场景，理论上更优但有最坏情况风险

掌握这两种解法，并能根据场景做出合理选择，是工程师算法能力的体现。