2024.1.23(347.前k个高频元素)

2024.1.23(347.前k个高频元素)

思路
这道题目主要涉及到如下三块内容：

1.要统计元素出现频率
2.对频率排序
3.找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。

什么是优先级队列呢？

其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

本题我们就要使用优先级队列来对部分频率进行排序。

为什么不用快排呢， 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

此时要思考一下，是使用小顶堆呢，还是大顶堆？

有的同学一想，题目要求前 K 个高频元素，那么果断用大顶堆啊。

那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

寻找前k个最大元素流程如图所示：（图中的频率只有三个，所以正好构成一个大小为3的小顶堆，如果频率更多一些，则用这个小顶堆进行扫描）

// 定义一个名为 Solution 的类
class Solution {
// 定义一个公共方法，返回一个整数数组，该方法接收两个参数：一个整数数组 nums 和一个整数 k
public int[] topKFrequent(int[] nums, int k) {
// 创建一个优先级队列 pq，用于存储整数数组，队列的排序规则是从大到小（根据数组的第二个元素）
// 这是为了避免使用复杂的 API 操作，因为优先级队列的特性是队首元素总是最小的（或者最大的，取决于排序规则）
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

    // 创建一个大小为 k 的整数数组 res，用于存储结果  
    int[] res = new int[k];  
      
    // 创建一个哈希映射 map，用于记录每个元素的出现次数  
    Map<Integer, Integer> map = new HashMap<>();  
      
    // 遍历输入数组 nums，统计每个元素的出现次数，并存储在哈希映射 map 中  
    for(int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);  
      
    // 遍历哈希映射的 entrySet，将每个元素及其出现次数转化为数组形式，并加入优先级队列 pq  
    for(var x : map.entrySet()) {   
        int[] tmp = new int[2];  
        tmp[0] = x.getKey(); // 当前元素的键（数字）  
        tmp[1] = x.getValue(); // 当前元素的值（出现次数）  
        pq.offer(tmp); // 将转化后的数组加入优先级队列 pq  
          
        // 如果优先级队列的大小超过了 k，则移除队首元素（即出现次数最少的元素）  
        if(pq.size() > k) {  
            pq.poll();  
        }  
    }  
      
    // 从优先级队列 pq 中取出前 k 个元素（即出现次数最多的 k 个元素），并存入结果数组 res  
    for(int i = 0; i < k; i ++) {  
        res[i] = pq.poll()[0]; // 取出的数组的第一个元素是数字本身，所以用 poll()[0] 获取这个数字  
    }  
      
    // 返回结果数组 res  
    return res;  
}  

}
这个代码的主要思路是利用优先级队列来存储出现次数最多的k个元素。由于优先级队列的特性，我们可以在添加新元素时保持队列的大小不超过k，同时保证了队首始终是出现次数最多的元素。这样，最后从队列中取出的就是出现次数最多的k个元素。