二刷 LeetCode：215. 数组中的第 K 个最大元素 347. 前 K 个高频元素 复盘笔记
目录
一、215. 数组中的第 K 个最大元素
题目回顾
思路复盘
方法 1：小顶堆（优先队列）
方法 2：快速选择（优化版快排）
易错点 & 二刷心得
二、347. 前 K 个高频元素
题目回顾
思路复盘
方法 1：哈希表 + 小顶堆
方法 2：桶排序
易错点 & 二刷心得
三、两道题的共性总结 & 二刷收获
这两道题是堆 / 优先队列的经典考点，也是面试中高频的 Top K 问题，二刷时我们重点拆解思路、对比不同解法，顺便把易错点和通用模板总结清楚。
一、215. 数组中的第 K 个最大元素
题目回顾
给定整数数组nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
思路复盘
这道题有两种主流解法：堆（优先队列）和快速选择，其中堆是面试中最常考的解法。
方法 1：小顶堆（优先队列）
核心思路：维护一个大小为k的小顶堆，遍历数组时：
- 如果堆的大小小于
k，直接将元素加入堆中 - 如果堆的大小等于
k，比较当前元素和堆顶元素：- 若当前元素大于堆顶元素，则弹出堆顶，加入当前元素
- 否则跳过
- 遍历结束后，堆顶元素就是第
k个最大的元素
Java 代码实现
java
运行
public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { if (minHeap.size() < k) { minHeap.offer(num); } else { if (num > minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } } return minHeap.peek(); }方法 2：快速选择（优化版快排）
核心思路：利用快排的分区思想，每次将数组分为两部分，根据基准元素的位置，缩小查找范围：
- 如果基准元素的位置等于
n-k，则基准元素就是答案 - 如果基准元素的位置大于
n-k，则在左半部分继续查找 - 如果基准元素的位置小于
n-k，则在右半部分继续查找
Java 代码实现
java
运行
public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k); } private int quickSelect(int[] nums, int left, int right, int targetIndex) { int pivotIndex = partition(nums, left, right); if (pivotIndex == targetIndex) { return nums[pivotIndex]; } else if (pivotIndex < targetIndex) { return quickSelect(nums, pivotIndex + 1, right, targetIndex); } else { return quickSelect(nums, left, pivotIndex - 1, targetIndex); } } private int partition(int[] nums, int left, int right) { int pivot = nums[right]; int i = left; for (int j = left; j < right; j++) { if (nums[j] <= pivot) { swap(nums, i, j); i++; } } swap(nums, i, right); return i; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }易错点 & 二刷心得
- 堆的选择：找第
k个最大元素用小顶堆，找第k个最小元素用大顶堆，不要搞混。 - 时间复杂度：小顶堆的时间复杂度是 O (nlogk)，快速选择的平均时间复杂度是 O (n)，最坏情况是 O (n²)，实际面试中优先推荐堆的解法。
- 边界处理：快速选择时，目标索引是
n-k，而不是k-1，注意区分从大到小和从小到大的排序。
二、347. 前 K 个高频元素
题目回顾
给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。
思路复盘
这道题是哈希表 + 堆的经典组合，也可以用桶排序的方法解决。
方法 1：哈希表 + 小顶堆
核心思路：
- 先用哈希表统计每个元素的出现频率
- 维护一个大小为
k的小顶堆，堆中元素按频率排序 - 遍历哈希表，将元素加入堆中，最终堆中的元素就是前
k个高频元素
Java 代码实现
java
运行
public int[] topKFrequent(int[] nums, int k) { // 1. 统计频率 Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } // 2. 小顶堆，按频率排序 PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue()); for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { if (minHeap.size() < k) { minHeap.offer(entry); } else { if (entry.getValue() > minHeap.peek().getValue()) { minHeap.poll(); minHeap.offer(entry); } } } // 3. 取出结果 int[] result = new int[k]; int index = 0; while (!minHeap.isEmpty()) { result[index++] = minHeap.poll().getKey(); } return result; }方法 2：桶排序
核心思路：
- 先用哈希表统计每个元素的出现频率
- 创建一个桶数组，桶的索引表示频率，桶中存放对应频率的元素
- 从后往前遍历桶数组，收集前
k个元素
Java 代码实现
java
运行
public int[] topKFrequent(int[] nums, int k) { // 1. 统计频率 Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } // 2. 创建桶 List<List<Integer>> buckets = new ArrayList<>(); for (int i = 0; i <= nums.length; i++) { buckets.add(new ArrayList<>()); } for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) { buckets.get(entry.getValue()).add(entry.getKey()); } // 3. 从后往前收集结果 int[] result = new int[k]; int index = 0; for (int i = buckets.size() - 1; i >= 0 && index < k; i--) { List<Integer> bucket = buckets.get(i); for (int num : bucket) { result[index++] = num; if (index == k) { break; } } } return result; }易错点 & 二刷心得
- 堆的比较器：在 Java 中，
PriorityQueue默认是小顶堆，所以自定义比较器时要按频率升序排列。 - 桶排序的适用场景：当元素频率分布较广时，桶排序的空间复杂度较高，但时间复杂度是 O (n)，效率更高。
- 结果顺序：题目不要求返回元素的顺序，所以两种方法的结果都可以直接返回，不需要额外排序。
三、两道题的共性总结 & 二刷收获
- Top K 问题的通用解法：
- 小顶堆：时间复杂度 O (nlogk)，空间复杂度 O (k)，适用于大部分场景
- 快速选择：平均时间复杂度 O (n)，空间复杂度 O (1)，适用于数组可修改的场景
- 桶排序：时间复杂度 O (n)，空间复杂度 O (n)，适用于频率分布较集中的场景
- 堆的核心思想：维护一个大小为
k的堆，用堆顶元素过滤掉不需要的元素，最终堆中保留的就是前k个元素。 - 面试重点：
- 第 K 个最大元素：堆的实现和快速选择的优化思路，以及时间复杂度分析
- 前 K 个高频元素：哈希表和堆的结合，桶排序的实现和适用场景