Java solution using max heap. O(unique_count + k * log (unique_count - k))


  • 0
    P
    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                if (map.containsKey(num)) {
                    map.put(num, map.get(num) + 1);
                } else {
                    map.put(num, 1);
                }
            }
            List<Integer> result = new LinkedList<>();
            int keySize = map.keySet().size();
            PriorityQueue<Pair> maxHeap = new PriorityQueue<>(keySize, (new Comparator<Pair>(){
                @Override
                public int compare(Pair p1, Pair p2) {
                    return p2.v - p1.v;
                }
            }));
            for (Integer key : map.keySet()) {
                maxHeap.add(new Pair(key, map.get(key)));
                if (maxHeap.size() > keySize - k) {
                    result.add(maxHeap.remove().k);
                }
            }
            return result;
        }
        
        class Pair {
            int k, v;
            Pair (int k, int v) {
                this.k = k;
                this.v = v;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.