Easy understanding Java Solution using Map and List.


  • 1
    S

    First I calculate the frequency of each number in the array, then build a bucket using the frequency as the key and the value as (numbers or elements) in a List. Lastly, I iterate though this map till k == 0 and find the most frequent elements.

    public class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
    		int length = nums.length;
    		Map<Integer, Integer> frequency = new HashMap<>();
    
    		for(int i = 0; i < length; ++i) {
    			if(!frequency.containsKey(nums[i])) {
    				frequency.put(nums[i],1);
    			}
    			else {
    				frequency.put(nums[i], frequency.get(nums[i]) + 1);
    			}
    		}
    
    		Map<Integer, List<Integer>> result = new HashMap<>();
    		List<Integer> temp = new ArrayList<Integer>();
    		int curFrequency = 0;
    		for(int key : frequency.keySet()) {
    			curFrequency = frequency.get(key);
    			if(!result.containsKey(curFrequency)) {
    				temp = new ArrayList<>();
    			}
    			else {
    				temp = result.get(curFrequency);
    			}
    			temp.add(key);
    			result.put(curFrequency, temp);
    		}
    
    		List<Integer> elements = new ArrayList<>();
    		int max = 0;
    		while(k > 0) {
    			max = 0;
    			for(int key : result.keySet()) {
    				max = Math.max(max, key);
    			}
    
    			temp = result.get(max);
    			for(int num : temp) {
    				elements.add(num);
    			}
    			k -= temp.size();
    			result.remove(max);
    		}
    		return elements;
    	}
    }
    

Log in to reply
 

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