/**
1. 分解为2个问题, 
    1.1 求元素频率  ->  HashMap统计一下 O(n)
    1.2 求最大的k个 ->  最小堆求topK    O(mlogk)

*/


class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        Queue<Integer> queue = new PriorityQueue<>((a,b)->(freq.get(a)-freq.get(b)));

        for (int i = 0 ; i < nums.length ; i++){
            Integer f = freq.get(nums[i]);
            if (f == null) freq.put(nums[i], 0);
            freq.put(nums[i], freq.get(nums[i]) + 1);
        }

        for (Integer num : freq.keySet()){
            if (queue.size() >= k &&  freq.get(num) <= freq.get(queue.peek())) continue;
            while (queue.size() >= k && freq.get(num) > freq.get(queue.peek())) queue.poll();
            queue.offer(num);
        }

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) result.add(queue.poll());
        return result;
    }
}