在这里插入图片描述

使用最小堆算法来解决这道题目:相当于有一个容量固定为K的教室,只能容纳 K 个人,学生们逐个逐个进入该教室,当教室容量达到K人之后,每次进入一个新的学生后,我们将分数最低的学生(类似本题中的频率最低元素)赶出去,最后所有学生都遍历结束之后,教室里所余的学生就是成绩前K高的学生们。

在这道题目中,最小堆(PriorityQueue)就像是一个只能容纳 K 个学生的教室,每次加入一个新的学生,教室满了就会将成绩最低的学生(即频率最低的元素)移除出去。最终剩下的 K 个学生,就是成绩最高的 K 个学生。

具体步骤如下:

  1. 我们先统计每个元素的出现频率(类似学生的分数)。
  2. 然后我们使用一个容量为 K 的最小堆来维护当前频率最高的 K 个元素。
    • 当堆的大小超过K时,将频率最低的元素移除,这样堆中始终只会保留频率最高的K个元素。
  3. 最后,堆中剩下的元素就是前K个高频元素。

这个方法的复杂度主要取决于建立和维护堆的过程,大概是O(N log K) 的时间复杂度,其中N是数组的长度,K是要返回的高频元素的个数。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //首先利用 Hashmap 统计每个数值的频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for(int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        //创建最小堆,存储键值对对象,key 代表元素,value 代表对应的频率值. 
        // 比较器 (a, b) -> a.getValue() - b.getValue() 隐式地比较了两个元素的频率 
        // 如果 a 的值(频率)小于 b,则 a 会排在 b 前面(因为最小堆会将频率最小的元素放在堆顶)
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(k, (a, b) -> a.getValue() - b.getValue());    
        //维护一个大小为 k 的最小堆
        for(Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            // 遍历插入一个新的键值对,而不是元素;键是唯一的,没有重复
            //由于堆顶元素始终是最小的元素,所以无论当前offer提供的待插入元素的大小与此时堆顶元素的大小如何,都会被插入堆中并自动调整。
            minHeap.offer(entry);
            if(minHeap.size() > k) { 
            
                minHeap.poll(); 
            }
        }

        int[] results = new int[k];
        for(int i = 0; i < k; ++i) {
            results[i] = minHeap.poll().getKey();
        }
        return results;
    }
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部