LeetCode347. 前 K 个高频元素

0 预备知识

0.1 Map中entrySet()方法使用

public Set> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。
就是返回一个集合，集合里存放的是对象，创建对象的类有两个属性，分别是 键和值 也即键值对。
其中Entry是属于Map的静态内部类，在创建Map对象的时候就会同时创建一个Entry对象，用来记录键与值的映射关系。

0.2 PriorityQueue优先级队列

PriorityQueue，即优先级队列。优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素（Java优先级队列默认每次取出来的为最小元素）。
大小关系： 元素的比较可以通过元素本身进行自然排序，也可以通过构造方法传入比较器进行比较。
PriorityQueue是Queen接口的一个实现类，而Queen接口是Collection接口的一个实现类，因此其拥有Collection接口的基本操作，此外，队列还提供了其他的插入，移除和查询的操作。PriorityQueue的peek和element操作的时间复杂度都为常数，add、offer、remove以及poll的时间复杂度是log(n)。

1 题目描述

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

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]
来源：力扣（LeetCode）
链接：347. 前 K 个高频元素

2 算法设计

2.1 使用map+list数组求解

算法思想： 首先通过map统计每个数字出现的频次，再通过list降序排序，最后输出前k个元素就是最大的前k个元素。

2.2 使用map+小顶堆（优先级队列）

算法思想： 同样需要用到map统计每个数字出现的字数，再初始化一个优先级队列，队列中的元素定义为一个二元组（num，cnt），队列中的元素按照cnt的值从小到大排序，最小的元素始终在队头（作为小顶堆，即最小的元素在堆顶），因为要求前k个出现的次数最多的元素，所以优先级队列中只需要维护前k个元素的顺序即可，最后剩下的也就是前k个出现次数最大的元素。

3 代码实现

解法一

    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < nums.length;i++){
           map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        //对map进行排序
        ArrayList<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries,((o1, o2) -> o2.getValue() - o1.getValue()));
        int[] res = new int[k];
        int ids = 0;
        for (int i = 0;i < k;i++){
            res[ids++] = entries.get(i).getKey();
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解法二

 public static int[] topKFrequent(int[] nums, int k) {
        //初始化map，统计数字出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //在优先队列中存储二元组(num,cnt)，cnt表示num元素出现的次数
        //出现次数按从队头到队尾的顺序是从小到大排列，出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((num1, num2) -> num1[1]-num2[1]);
        //小顶对只需要维持k个元素有序即可
        for (Map.Entry<Integer,Integer> entry:map.entrySet()){
            if (pq.size() < k){  //小顶堆元素个数小于k时直接相加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            }else {
                //当前元素出现的次数大于小顶堆的根节点
                if (entry.getValue() > pq.peek()[1]){
                    //弹出队头（小顶堆的根节点），把堆里出现次数最少的那个删除，留下的就是次数最多的元素了
                    pq.poll();
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        int[] res = new int[k];
        //依次弹出小顶堆,这里先弹出的是堆的根，及出现次数最少的元素先弹出
        for (int i = 0;i < k;i++){
            res[i] = pq.poll()[0];
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

4 结果