Solution with Max(n, k*log(k)) time complexity


  • -1
    X
    public class Solution {
      public List<Integer> topKFrequent(int[] nums, int k) {
    	List<Integer> rs = new ArrayList<Integer>();
    	
    	if(nums == null || nums.length == 0) {
    		return rs;
    	}
    	
    	HashMap<Integer, Integer> mapA = new HashMap<Integer, Integer>();
    	for(int i = 0; i < nums.length; i++) {
    		if(!mapA.containsKey(nums[i])) {
    			mapA.put(nums[i], 0);
    		}
    		
    		mapA.put(nums[i], mapA.get(nums[i]) + 1);
    	}
    	
    	List<Integer> values = new ArrayList<Integer>(mapA.values());
    	Collections.sort(values, Collections.reverseOrder());
    	
    	int i = 0;
    	while(k != 0) {
    		k--;
    		i++;
    	}
    	
    	int least = values.get(i - 1);
    	
    	for(int key : mapA.keySet()) {
    		if(mapA.get(key) >= least) {
    			rs.add(key);
    		}
    	}
    	
    	return rs;
    }
    

    }


  • 0
    N

    Collections.sort(values, Collections.reverseOrder());

    isn't this require nlogn? so why Max(n, klog(k))?


Log in to reply
 

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