【大根堆 Java】使用优先队列+HashMap 解决前 K 个高频元素问题

一、题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例

二、思路

本题我们主要完成两个步骤：

1. 统计出每个元素出现的次数
2. 找出出现次数最多的前 K 个元素

• 对第一个步骤，我们可以使用 HashMap 进行统计，统计方法如下：

这一步中，最需要学习的就是 getOrDefault() 的使用，其若是在 map 中找对对应 key 的 value，则返回 value 值，否则返回我们设置的默认值

        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0));
        }
1
2
3
4

• 对第二个步骤 ——
  1.首先我们建立一大根堆，建立方式为使用 Java 语言为我们提高的优先队列 PriorityQueue
  2.然后我们将上面步骤得到的 HashMap 中的每个映射存放到这个优先队列中
  3.从优先队列中取出前 K 个元素

扩展知识：

优先队列中存储的类型为 Map.Entry ， —— 这个 Map.Entry 是什么？

答： Map中存放的元素均为键值对，每一个键值对必然存在一个映射关系 ，Map中采用Entry内部类来表示一个映射项，映射项包含Key和Value

也就是说 每一个键值对就是一个Entry，Map.Entry里面包含getKey()和getValue()方法

第二步代码：

      Set<Map.Entry<Integer, Integer>> entries = map.entrySet(); // 用于遍历向大根堆中加入键值对
      // 根据map中的value值，构建于一个大顶堆（o1 - o2: 小根堆， o2 - o1 : 大根堆）
      PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
      for (Map.Entry<Integer, Integer> entry : entries) { // 将键值对加入大根堆中
          queue.offer(entry);
      }
      for (int i = k - 1; i >= 0; i--) { // 取出前K个元素
          result[i] = queue.poll().getKey();
      }
1
2
3
4
5
6
7
8
9

三、完整代码

    public int[] topKFrequen2(int[] nums, int k) {
        int[] res = new int[k];

        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0));
        }
        
        Set<Map.Entry<Integer, Integer>> set = map.entrySet();
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((o1, o2) -> (o2.getValue() - o1.getValue()));
        for(Map.Entry<Integer, Integer> entry: set){
            priorityQueue.add(entry);
        }
        
        for(int i=0; i<=k; i++){
            res[i] = priorityQueue.poll().getKey();
        }
        
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20