347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

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

Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements.

Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

There is one case, if two value has same count.

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : nums){
            if(map.containsKey(val)){
                map.put(val, map.get(val) + 1);
            }else{
                map.put(val, 1);
            }
        }

        class Pair{
            int key;
            int count;
            Pair(int k, int c){
                key = k;
                count = c;
            }
        }

        Comparator<Pair> comp = new Comparator<Pair>(){
            @Override
            public int compare(Pair p1, Pair p2){
                if(p1.count != p2.count) return p1.count - p2.count;
                else return p1.key - p2.key;
            }
        };

        PriorityQueue<Pair> queue = new PriorityQueue<>(k, comp);

        for(int val : nums){
            if(!map.containsKey(val)) continue;
            int count = map.get(val);
            Pair p = new Pair(val, count);
            if(queue.size() < k){
                queue.offer(p);
            }else{
                Pair top = queue.peek();
                if(p.count > top.count){
                    queue.poll();
                    queue.offer(p);
                }
            }
            map.remove(val);
        }
        List<Integer> res = new ArrayList<>();
        for(Pair p : queue){
            res.add(p.key);
        }
        return res;

    }
}