Java Solution. Use HashMap and PriorityQueue


  • 4
    Z
    public class Solution {
        // supply a new implementation for Map.Entry Comparator
        class EntryComparator<K, V extends Comparable<V>> 
        implements Comparator<Map.Entry<?, V>> {
           public int compare(Map.Entry<?, V> left, Map.Entry<?, V> right) {
                // Call compareTo() on V, which is known to be a Comparable<V>
                return right.getValue().compareTo(left.getValue());
         }   
        }
        
        public List<Integer> topKFrequent(int[] nums, int k) {
            // Priority Queue's size is k, hence the run time for this case is just O(lgK).
            PriorityQueue<Map.Entry<Integer, Integer>> kFrequent = new PriorityQueue<>(k,
                                                                                       // override Comprator class 
                                                                                       new Comparator<Map.Entry<Integer, Integer>>() {
                                                                                          public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer>right){
                                                                                               return right.getValue().compareTo(left.getValue());
                                                                                           }
                                                                                       }
                                                                                       );
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i : nums){
                map.putIfAbsent(num, 0);
               // if key is already in the map, then increase the counter
                map.computeIfPresent(num, (key, oldVal) -> oldVal + 1);
            }
            //use priority queue to find kFrequent
            for(Map.Entry<Integer, Integer> mapEntry : map.entrySet()){
                kFrequent.offer(mapEntry);
            }
            List<Integer> returnList = new ArrayList<>();
            for(int i = 0; i < k; i++){
                // in practice, we need check operation is null or not
                //System.out.println(kFrequent.poll());
                returnList.add(kFrequent.poll().getKey());
            }
            return returnList;
        }
    }

  • 0
    O

    @zhexuany This is O(nlgn), not the O(nlgk) because you added all the map entry to the queue. The first argument in PriorityQueue constructor is just init capacity.

    for(Map.Entry<Integer, Integer> mapEntry : map.entrySet()){
        if (kFrequent.size() == k && kFrequent.peek().getValue < mapEntry.getValue()) kFrequent.poll();
        if (kFrequent.size() < k) kFrequent.offer(mapEntry);
    }
    

    And to make this work you will need to change the PriorityQueue a Min-Heap by changing the comparator:

    PriorityQueue<Map.Entry<Integer, Integer>> kFrequent = new PriorityQueue<>(k, new Comparator<Map.Entry<Integer, Integer>>() {
        public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer>right) {
            return left.getValue().compareTo(right.getValue());
        }
    });
    
    

Log in to reply
 

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