Java Solution using Hash Map and Priority Queue


  • 0

    Hello everyone,

    I present you my solution, using a hash map and priority queue. First we count the frequency of each number, such that the key is the number and the frequency is the value in the hash map. After that, we create a priority queue of map entries, ordered with respect to the value of the map entry, i.e. the frequency in this case. In the end we just pop the first k elements from the priority queue.

    Here is the code:

     public List<Integer> topKFrequent(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            
            // count frequency
            for(int n : nums){
                map.put(n, map.getOrDefault(n, 0) + 1);
            }
            
            // create priority queue, ordering map entries with respect to the frequency
            PriorityQueue<Map.Entry<Integer, Integer>> queue = 
            new PriorityQueue<Map.Entry<Integer, Integer>>(new Comparator<Map.Entry<Integer, Integer>>()
            {
               @Override
               public int compare(Map.Entry<Integer, Integer> entry1, Map.Entry<Integer, Integer> entry2)
                 {
                    return entry2.getValue() - entry1.getValue();
                 }
            });
        
            
            // insert in the queue
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                queue.offer(entry);
            }
            
            // poll the top k
            List<Integer> list = new LinkedList<Integer>();
            for(int i = 0; i < k; i ++){
                Map.Entry<Integer, Integer> entry = queue.poll();
                list.add(entry.getKey());
            }
            
            return list;
        }
    

  • 0
    V

    @IlievskiV shouldn't use maxheap . will cause a lot of space waste


Log in to reply
 

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