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.

 to see which companies asked this question

1 public class Solution { 2     public List
      
        topKFrequent(int[] nums, int k) { 3         HashMap
       
         map = new HashMap
        
         (); 4         ArrayList
         
          [] bucket = new ArrayList[nums.length+1]; 5         for(int n : nums){ 6             map.put(n,map.get(n) == null ? 1 : map.get(n)+1); 7         } 8         for(int key : map.keySet()){ 9             int cnt = map.get(key);10             if(bucket[cnt] == null){11                 bucket[cnt] = new ArrayList<>();12             }13             bucket[cnt].add(key);14         }15         List
          
            ans = new ArrayList
           
            ();16 for(int i = bucket.length-1;i>=0;i--){17 if(bucket[i] != null){18 ans.addAll(bucket[i]);19 if(ans.size() >= k) break;20 }21 }22 return ans;23 }24 }
           
          
         
        
       
      

最初的想法是 使用hashmap 记录频率，之后再按频率大小逆序输出k个元素。之后参考 discuss 中的代码，使用bucket来降低时间复杂度达到O(n)。