当前位置：首页 > article >正文

栈和队列-前K个高频元素

article 2025/2/22 5:30:06

代码随想录-刷题笔记

347. 前 K 个高频元素 - 力扣（LeetCode）

内容:

该问题也是一个数据结构的特化问题，只要掌握优先级队列-也就是堆的话可以很快的解决问题。

本题我采用大根堆来解决，大根堆就是一个二叉树，自带排序的二叉树，大根堆可以保证根的值是最大的，第二大的是根的左子树，第三大的是根的右子树，以此类推.按照层序遍历的结构来排列大小。

如果想要解决本题，还真需要理明白 ,只要思路清晰，跟开发业务一样，基本上没什么难的，一步一步来就可以了

1.使用map 来映射值和出现频率 , k - f

2.对出现频率进行堆排序

3.取堆排序后的前k个结果.

好了，已经理清楚了，按照这三步可以完美的写出问题

代码:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < nums.length ; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> maxHeap = new PriorityQueue<>((a,b) -> b.getValue()-a.getValue());
        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
            maxHeap.add(entry);
        }
        for(int i = 0 ; i < k ; i++) {
            Map.Entry<Integer,Integer> val = maxHeap.poll();
            result.add(val.getKey());
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}