347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution:

HashMap and bucket sort

Use a hashmap to track frequencies of all elements. Because the maximum possible frequencies will be the number of elements, we can use bucket to get all elements that occur certain times. Either an array or a list can present the bucket. 

Finally, we retrieve the top K elements from the top of the bucket.

Time complexity: O(n)

 public List<Integer> topKFrequent(int[] nums, int k) {  
     List<Integer> res=new ArrayList<Integer>();  
     Map<Integer,Integer> map=new HashMap<Integer,Integer>();  
     for(int i=0;i<nums.length;i++){  
       map.put(nums[i],map.getOrDefault(nums[i],0)+1);  
     }  
     List<List<Integer>> frequencies=new ArrayList<List<Integer>>();  
     for(int i=0;i<nums.length;i++) frequencies.add(new ArrayList<Integer>());  
     for(Map.Entry<Integer,Integer> pair : map.entrySet()){  
       frequencies.get(pair.getValue()-1).add(pair.getKey());  
     }  
     for(int i=nums.length-1;i>=0;i--){  
       for(int j:frequencies.get(i)) res.add(j);  
       if(res.size()==k) return res;  
     }  
     return res;  
   }