leetcode高频100题(leetcode 频率)

JAVA优先级队列元素输出顺序测试
Java @Override的作用(重写需要注意的 注释)
Java中PriorityQueue的排序
挺难的，主要要了解优先队列用法，重写用法，堆的原理。
优秀解答1：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //设置一个map集合,key存放数字,value存放出现次数
        Map map = new HashMap<>();
        //统计出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从小到大排序
        PriorityQueue queue = new PriorityQueue<>(new Comparator(){
            public int compare(Integer a,Integer b){
                return map.get(a) - map.get(b);
            }
        });
        //将map中的数字,插入到大根堆中
        for(Integer key:map.keySet()){
            if(queue.size() < k){
                queue.add(key);
            }else if(map.get(key) > map.get(queue.peek())){
                queue.poll();
                queue.add(key);
            }
        }
        //将大根堆中的k个数字放到数组中
        int [] res = new int[k];
        int index = 0;
        while(!queue.isEmpty()){
            res[index++] = queue.poll();
        }
        return res;
    }
}

优秀解答2：

class Solution {
    public List topKFrequent(int[] nums, int k) {
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
               map.put(num, map.get(num) + 1);
             } else {
                map.put(num, 1);
             }
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 取出最小堆中的元素
        List res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove());
        }
        return res;
    }
}


作者：cxywushixiong
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的解法：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //1.hashmap来统计频次
        HashMap map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i])+1);
            }
            else{
                map.put(nums[i],1);
            }
        }
        //2.优先队列放入前k频次的数，原理是小根堆  (需要重写Override优先队列的排序方法)
        Comparator cmp = new Comparator<>(){
            @Override
            public int compare(Integer a, Integer b){
                return map.get(a) - map.get(b);
            }
        };
        PriorityQueue pq = new PriorityQueue<>(cmp);//cmp指定由value的小到大排序，越小越靠前
        for(Integer key : map.keySet()){
            if(pq.size() < k) pq.add(key);
            else if(map.get(key) > map.get(pq.peek())){
                pq.poll();//把对头小频次的key出列
                pq.add(key);
            }
        }
        System.out.println(pq);
        //3.输出前k个数
        int[] res = new int[pq.size()];
        int size = pq.size();//注意size会变化，不要写到循环里面
        for(int i = 0; i < size; i++){
            res[i] = pq.poll();
        }
        return res;
    }
}