Simple Java Solution using HashMap and TreeMap (40ms)


  • 0
    G

    Idea similar to bucket sort but I used reverse Ordered TreeMap instead of an array:

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer,Integer> hm = new HashMap<>();
            Map<Integer,List<Integer>> tm = new TreeMap<>(Collections.reverseOrder());
            
            // Process all numbers and count their frequencies
            for(int n : nums){
                if(hm.containsKey(n)){
                    hm.put(n,hm.get(n)+1);
                } else {
                    hm.put(n,1);
                }
            }
            
            // Now make frequencies as key's of reverse ordered treemap and make list of numbers with same freq
            List<Integer> ls;
            for(int num : hm.keySet()){
                int freq = hm.get(num);
                if(tm.containsKey(freq)){
                    ls = tm.get(freq);
                } else {
                    ls = new ArrayList<Integer>();
                }
                ls.add(num);
                tm.put(freq,ls);
            }
            
            // Iterate through treemap and add top k elements into result lists
            List<Integer> res = new ArrayList<Integer>(k);
            outer:
            for(int freq : tm.keySet()){
                ls = tm.get(freq);
                for(int n : ls){
                    res.add(n);
                    if(res.size()==k){
                        break outer;
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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