目录一、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) { PriorityQueueInteger 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. 统计频率 MapInteger, Integer freqMap new HashMap(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) 1); } // 2. 小顶堆按频率排序 PriorityQueueMap.EntryInteger, Integer minHeap new PriorityQueue((a, b) - a.getValue() - b.getValue()); for (Map.EntryInteger, 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. 统计频率 MapInteger, Integer freqMap new HashMap(); for (int num : nums) { freqMap.put(num, freqMap.getOrDefault(num, 0) 1); } // 2. 创建桶 ListListInteger buckets new ArrayList(); for (int i 0; i nums.length; i) { buckets.add(new ArrayList()); } for (Map.EntryInteger, 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--) { ListInteger 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 个高频元素哈希表和堆的结合桶排序的实现和适用场景