2021-09-29-前k个高频元素

思路

统计每个元素出现的次数
遍历map，用最小堆保存频率最大的k个元素

代码

class Solution {
    // HashMap<Integer, Integer> map;
    // static Comparator<Integer> cmp = new Comparator<>(){
    //     public int compare(Integer o1, Integer o2){
    //         return map.get(o1)-map.get(o1);
    //     }
    // };
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计每个元素出现的次数
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return map.get(o1)-map.get(o2);
            }
        });
        for (Integer key: map.keySet()){
            if (queue.size()<k){
                queue.add(key);
            }else{
                queue.add(key);
                queue.poll();
            }
        }
        List<Integer> res = new ArrayList<>();
        while (queue.size()>0){
            res.add(queue.poll());
        }
        return res;
    }
}