Java O(N) solution, map + bucket


  • 0
    M
        public List<Integer> topKFrequent(int[] nums, int k) {
        	if(nums==null || nums.length==0) return new LinkedList<Integer>();
        	Map<Integer, Integer> map = new HashMap<>();//<Ele, Times>
        	int times=0, max = 0;
        	for(int ele : nums){
        		times = map.getOrDefault(ele, 0)+1;
        		map.put(ele, times);
        		max = Math.max(max, times);
        	}
        	List<Integer>[] bucket = new LinkedList[max+1];
        	Integer mapVal = 0;
        	for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        		mapVal = entry.getValue();
        		if(bucket[mapVal]==null) bucket[mapVal] = new LinkedList<Integer>();
        		bucket[mapVal].add(entry.getKey());
        	}
        	List<Integer> res = new LinkedList<>();
        	for(int i=bucket.length-1; i>=0 && res.size()<k; i--){
        		if(bucket[i]!=null)
        			res.addAll(bucket[i]);
        	}
        	return res;
        }
    

Log in to reply
 

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