Java easy-understand solution with explanation


  • 0
    H

    We need to find the top k frequent elements. The best way to find a set of largest or smallest elements is to use a heap. Here, we need the most frequent ones. So, first we scan the entire array and create a count hashtable for it. And then, we maintain a heap of size k which has the top K elements at all times. We go over the count hashtable one by one and add it to the heap until we have k elements. After this, when we get a new element, we check the top of heap which is the minimum count element in the heap and if the current element occurs more than the min, we replace it.

    public class Solution {
        class Pair{
            int count, val;
        }
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
            for(int num: nums){
                Integer count = hash.get(num);
                if(count != null){
                    hash.put(num, count + 1);
                } else {
                    hash.put(num, 1);
                }
            }//counting done
            
            PriorityQueue<Pair> heap = new PriorityQueue<Pair>(k, new Comparator(){
                public int compare(Object o1, Object o2){
                    Pair a = (Pair) o1;
                    Pair b = (Pair) o2;
                    if(a.count < b.count){
                        return -1;
                    } else if(a.count == b.count){
                        return 0;
                    }
                    return 1;
                }
            });
            
            for(Map.Entry<Integer, Integer> keyVal: hash.entrySet()){
                if(heap.size() < k){
                    Pair p = new Pair();
                    p.val = keyVal.getKey();
                    p.count = keyVal.getValue();
                    heap.add(p);
                } else {
                    Pair top = heap.peek();
                    Integer count = keyVal.getValue();
                    if(top.count < count){
                        heap.poll();
                        Pair p = new Pair();
                        p.val = keyVal.getKey();
                        p.count = keyVal.getValue();
                        heap.add(p);
                    }
                }
            }
            
            List<Integer> topK = new ArrayList<Integer>();
            while( !heap.isEmpty()){
                Pair top = heap.poll();
                topK.add(top.val);
            }
            
            return topK;
        }
    }
    

Log in to reply
 

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