Accepted Java Solution


  • 0
    M

    1 use PriorityQueue to build a max heap (34ms)

    public List<Integer> topKFrequent(int[] nums, int k) {
        //1. Create a hashmap where an item and its frequency are stored.
        HashMap<Integer, Integer> map = new HashMap<>();
        
        //2. Walk through nums, count its frequency, store them in the map
        for(int n:nums)
            map.put(n, map.getOrDefault(n,0)+1);
        
        //3. Create a PriorityQueue for building MaxHeap
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(map.size(), new Comparator<Map.Entry<Integer,Integer>>(){
           public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
               return o2.getValue()-o1.getValue();
           } 
        });
        
        for(Map.Entry<Integer, Integer> e : map.entrySet())
            pq.add(e);
            
        //4.Build an array which will be returned with top K elements
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<k;i++){
            ret.add(pq.poll().getKey());
        }
        return ret;
        
    }
    

    2 Use an array and sort it (45ms)

    public List<Integer> topKFrequent(int[] nums, int k) {
        //1. Create a hashmap where an item and its frequency are stored.
        HashMap<Integer, Integer> map = new HashMap<>();
        
        //2. Walk through nums, count its frequency, store them in the map
        for(int n:nums){
            if(map.containsKey(n)){
                map.put(n, map.get(n)+1);
            }else{
                map.put(n,1);
            }
        }
        //3. Sort Entries of the map using Collections.sort in ascending order on its value
        List<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer,Integer>>(){
           public int compare(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2){
               return o2.getValue() - o1.getValue();
           } 
        });
        
        //4.Build an array which will be returned with top K elements
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<k;i++){
            ret.add(list.get(i).getKey());
        }
        return ret;
        
    }

  • 0
    J

    For your PriorityQueue solution, here are a couple minor improvements for readability.

    Instead of:

    for(Map.Entry<Integer, Integer> e : map.entrySet())
        pq.add(e);
    

    just use:

    pq.addAll(map.entrySet());
    

    Instead of:

    return o2.getValue() - o1.getValue();
    

    just use:

    return o2.getValue().compareTo(o1);
    

Log in to reply
 

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