leetcode347 前K个高频元素

核心思路：小顶堆 (Min-Heap)

我们可以利用 优先队列 (Priority Queue) 来解决这个问题。

1. 统计频率：使用哈希表 (HashMap) 统计每个数字出现的次数。

2. 维护堆：建立一个大小为 k 的小顶堆。

   • 遍历哈希表中的元素。
   • 将元素加入堆中。
   • 如果堆的大小超过了 k，则将堆顶元素（当前堆中频率最小的那个）弹出。
   • 原理：因为是小顶堆，堆顶永远是“目前前 k 个里频率最低的”。把最小的踢走，剩下的自然就是频率最高的 k 个。

3. 输出结果：最后堆中留下的 k 个元素就是答案。

   
   import java.util.HashMap;
   import java.util.Map;
   import java.util.PriorityQueue;
   
   class Solution {
       public int[] topKFrequent(int[] nums, int k) {
           // 1. 使用 HashMap 统计每个元素出现的频率
           Map<Integer, Integer> countMap = new HashMap<>();
           for (int num : nums) {
               countMap.put(num, countMap.getOrDefault(num, 0) + 1);
           }
   
           // 2. 初始化优先队列 (小顶堆)
           // 比较器逻辑：根据 Map 中的 value (频率) 进行升序排序
           // (a, b) -> countMap.get(a) - countMap.get(b) 表示频率小的在堆顶
           PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> countMap.get(a) - countMap.get(b));
   
           // 3. 遍历 Map，维护一个大小为 k 的堆
           for (int key : countMap.keySet()) {
               // 入堆
               pq.offer(key);
               
               // 如果堆的大小超过 k，弹出频率最小的元素 (堆顶)
               if (pq.size() > k) {
                   pq.poll();
               }
           }
   
           // 4. 取出堆中的结果
           int[] res = new int[k];
           for (int i = 0; i < k; i++) {
               // 依次弹出堆中元素
               res[i] = pq.poll();
           }
           
           return res;
       }
   }
   

   从这个题，学一下hashmap遍历可以用map.keySet（）来获取所有的key

假设我们要比较 a 和 b：

• 想从小到大排 (升序/小顶堆)：写 a - b
• 想从大到小排 (降序/大顶堆)：写 b - a

就这么简单！

入堆是offer，出堆是poll