[JAVA] Use map to count and array to collect k from largest / T : O(N), S : O(N)


  • 0
    J
    class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> result = new ArrayList<Integer>();
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            int max = 0;
            
            for(int num : nums){
                int val = map.getOrDefault(num, 0) + 1;
                if(max < val)
                    max = val;
                map.put(num, val);
            }
            
            List<Integer>[] lsts = new ArrayList[max];
            for(int key : map.keySet()){
                int index = map.get(key)-1;
                if(lsts[index] == null){
                    lsts[index] = new ArrayList<Integer>();
                }
                lsts[index].add(key);
            }
            
            int index = max-1;
            while(k > 0 && index >= 0){
                if(lsts[index] != null){
                    for(int elem : lsts[index]){
                        result.add(elem);
                        k--;
                    }
                }
                index--;
            }
            return result;
        }
    }
    

Log in to reply
 

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