Top K Frequent Elements

Given a non-empty array of integers, return thekmost frequent elements.

For example,
Given[1,1,1,2,2,3]and k = 2, return[1,2].

分析

heap sort 就是用heap来做sort

HeapSort 一定热身题，不解释，直接写码

什么时候用HeapSort ? 实际中，若n为一百万， 只要求找出100个最大的，比如求K个最大（K个最小） ，则Heap Sort好用。但其他情况下，能用quick sort 或者 merge sort就不要用heap sort（因为heap sort内部构建了一颗树，原子操作太多）

heap sort 就是用heap来做sort

代码

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numFreqs = new HashMap();

        for(int num : nums){
            numFreqs.put(num, numFreqs.containsKey(num) ? numFreqs.get(num) + 1 : 1);
        }

        PriorityQueue <Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((entry1, entry2) -> entry1.getValue() - entry2.getValue());


        for(Map.Entry<Integer, Integer> entry : numFreqs.entrySet()){
            if(minHeap.size() < k){
                minHeap.add(entry);
            }else if(entry.getValue() > minHeap.peek().getValue()){
                minHeap.poll();
                minHeap.add(entry);

            }
        }

        List<Integer> result = new LinkedList<>();
        while(!minHeap.isEmpty() && result.size() < k){
            result.add(0, minHeap.poll().getKey());
        }
        return result;

    }
}