三刷。

准备面试正好有这个题，把3种方式都撸一下试试。

先是Bucket Sort。因为我们知道所有数据(frequency)的值域：最小是0，element在数组中一次都未出现；最大是数组长度，整个数组只含此element，有了值域就适合Bucket。

前面按出现频率建map，记录每个int出现了多少次，然后按照出现次数入桶int[] bucket，最后倒着遍历，只要桶不是空的就把里面元素加到解里，K个解之后返还。

Time: 建图O(n)，入桶O(n)，最后检查桶，也是O(n). 最后是O(n)

Space: map O(n), bucket array O(n). 最后O(n)

public class Solution {    public List
    
      topKFrequent(int[] nums, int k) {        List
     
       res = new ArrayList<>();        if (k == 0 || nums.length == 0) return res;                Map
      
        map = new HashMap<>();        for (int i : nums) {            map.put(i, map.getOrDefault(i, 0) + 1);        }                List
       
        [] bucket = new List[nums.length + 1];        for (int i : map.keySet()) {            int val = map.get(i);            if (bucket[val] == null) {                bucket[val] = new ArrayList
        
         ();            }            bucket[val].add(i);        }                for (int i = bucket.length - 1; i >= 0; i--) {            if (bucket[i] != null) {                res.addAll(bucket[i]);                k -= bucket[i].size();                if (k == 0) break;            }        }                return res;    }}
        
       
      
     
    

方法二：

Max Heap:

首先还是建图，然后按照出现频率放到maxHeap里，然后取出TOP K个就行了，很直接。

Time: 建图O(n) 入pq是 O(n*lgn) TOP K个是 O(klgn) O(n + (n+k)lgn)

Space: 图O(n)，PQ takes O(n)

public class Solution {    public List
    
      topKFrequent(int[] nums, int k) {        List
     
       res = new ArrayList<>();        if (k == 0 || nums.length == 0) return res;                Map
      
        map = new HashMap<>();        for (int i : nums) {            map.put(i, map.getOrDefault(i, 0) + 1);        }                PriorityQueue
       
         pq = new PriorityQueue
        
         (new Comparator
         
          () { public int compare(Integer a, Integer b) { return -Integer.compare(map.get(a), map.get(b)); } }); for (int i : map.keySet()) { pq.offer(i); } for (int i = 0; i < k ; i++) { res.add(pq.poll()); } return res; }}
         
        
       
      
     
    

方法三：

MinHeap

前面一样，是miniHeap，队列最前是出现频率最小的element，而且一旦队列size大于K，直接POLL顶端，因为最小的不可能是要求的元素。

Time: 图 O(n)， PQ入各种数字，然后保持K的大小应该是(n-k)lgK + KlgK(最后一个似乎可以省略，直接加PQ是可以的）

O(n + (n-KlgK)

public class Solution {    public List
    
      topKFrequent(int[] nums, int k) {        List
     
       res = new ArrayList<>();        if (k == 0 || nums.length == 0) return res;                Map
      
        map = new HashMap<>();        for (int i : nums) {            map.put(i, map.getOrDefault(i, 0) + 1);        }                PriorityQueue
       
         pq = new PriorityQueue
        
         (k, new Comparator
         
          () { public int compare(Integer a, Integer b) { return Integer.compare(map.get(a), map.get(b)); } }); for (int i : map.keySet()) { pq.offer(i); if (pq.size() > k) { pq.poll(); } } res.addAll(pq); return res; }}