TopK算法

Top K Frequent Elements

这种问题一般有两种做法，一是建立一个wrapper class统计频率,然后用heap得到topK.

二是bucket sort.bucket的index就是频率，里面放的是对应的值。

PQ的做法

public class Solution {
    // error-prone Comparable<Node>
    class Node implements Comparable<Node> {
        int key;
        int freq;
        public Node(int key, int freq) {
            this.key = key;
            this.freq = freq;
        }

        public int compareTo(Node a) {
            return a.freq - this.freq;
        }
    }

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

        for(int num : nums) {
            if(!map.containsKey(num)) {
                map.put(num, new Node(num, 1));
            } else {
                Node t = map.get(num);
                t.freq++;
                map.put(num, t);
            }
        }

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

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

        return result;
    }
}