Frequency 类问题

Top K Frequent Elements

简单写法, 需要掌握用hashmap做heap的element

    public List<Integer> topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int n : nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<Map.Entry<Integer, Integer>>((o1, o2)->o2.getValue()-o1.getValue());
        pq.addAll(map.entrySet());

        List<Integer> ret = new ArrayList<Integer>();
        for(int i=0;!pq.isEmpty() &&i<k;i++){
            ret.add(pq.poll().getKey());
        }
        return ret;
    }

速度尚可，超过65.15%

public class Solution {
    private class Node implements Comparable<Node>{
        int key;
        int frequency;
        public Node(int key, int frequency){
            this.key = key;
            this.frequency = frequency;
        }
        public int compareTo(Node a){
            return a.frequency - this.frequency;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        PriorityQueue<Node> maxHeap = new PriorityQueue<Node>();
        HashMap<Integer, Node> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i], new Node(nums[i], 1));
            } else {
                Node node = map.get(nums[i]);
                node.frequency ++;
                map.put(nums[i], node);
            }
        }

        for(Integer key : map.keySet()){
            maxHeap.offer(map.get(key));
        }

        for(int i = 0; i < k; i++){
            list.add(maxHeap.poll().key);
        }

        return list;
    }
}