# 0347. Top K Frequent Elements
###### tags: `Leetcode` `Medium` `Top K Elements` `FaceBook`
Link: https://leetcode.com/problems/top-k-frequent-elements/
## 思路
### 思路一 Priority Queue
很简单的思路，但是要**注意语法 priority queue的声明，以及如何定义排序方法**
先遍历一遍，然后用Map存每个数出现的次数
再用priority queue对出现的次数排序
如果queue的size大于k就用poll()把多余的扔掉
### 思路二 Quick sort
### 思路三 Bucket Sort
但桶排序只适用于最大值比较小的情况，如果是找top k 大的值，用桶排序时间和空间复杂度就会比较高，因为array会非常大
先用map统计count，然后用一个array of list存每个频率对应的数字们
**注意array of list的声明 ```List<Integer>[] bucket = new List [nums.length+1];```**
## Code in Java
### 思路一

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> count = new HashMap();
        for(int n:nums){
            count.put(n,count.getOrDefault(n,0)+1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                (n1,n2) -> count.get(n1)-count.get(n2)
        );
        for(int n:count.keySet()){
            queue.add(n);
            if(queue.size()>k){
                queue.poll();
            }
        }

        int[] top = new int[k];
        for(int i = k-1;i >= 0;i--){
            top[i] = queue.poll();
        }
        return top;
    }

### 思路二

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> count = new HashMap();
        for(int n:nums){
            count.put(n,count.getOrDefault(n,0)+1);
        }
        List<int[]> values = new ArrayList<int[]>();
        for (Map.Entry<Integer,Integer> entry:count.entrySet()){
            int key = entry.getKey();
            int val = entry.getValue();
            values.add(new int[]{key,val});
        }
        int[] ret = new int[k];
        qsort(values,0,values.size()-1, k, ret, 0);
        return ret;
    }
    public static void qsort(List<int[]> values, int start, int end, int k, int[] ret, int retIndex){
        int picked = (int)(Math.random()*(end-start+1))+start;
        Collections.swap(values,picked,start);

        int pivot = values.get(start)[1];
        int index = start;
        for(int i = start+1;i <= end;i++){
            if(values.get(i)[1]>pivot){
                Collections.swap(values,index+1,i);
                index++;
            }
        }
        Collections.swap(values,start,index);

        if(index-start+1<=k){
            for(int i = start;i <= index;i++){
                ret[retIndex++] = values.get(i)[0];
            }
            if(k>index-start+1){
                qsort(values, index+1, end, k-(index-start+1), ret, retIndex);
            }
        }
        else{
            qsort(values, start, index-1, k, ret, retIndex);
        }
    }
}

### 思路三

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            count.put(nums[i], count.getOrDefault(nums[i],0)+1);
        }
        List<Integer>[] bucket = new List [nums.length+1];
        for(int key:count.keySet()){
            int frequency = count.get(key);
            if(bucket[frequency]==null) bucket[frequency] = new ArrayList<>();
            bucket[frequency].add(key);
        }
        int[] ans = new int[k];
        int idx = 0;
        for(int i = bucket.length-1; i >= 0 && idx < k;i--){
            if(bucket[i]!=null){
                for(int j = 0; j < bucket[i].size() && idx < k;j++){
                    ans[idx++] = bucket[i].get(j);
                }
            }
        }
        return ans;
    }
}

## Result
### 思路一
Runtime: 11 ms, faster than **55.15%** of Java online submissions for Top K Frequent Elements.
Memory Usage: 41.5 MB, less than **82.08%** of Java online submissions for Top K Frequent Elements.
### 思路二
Runtime: 9 ms, faster than **87.07%** of Java online submissions for Top K Frequent Elements.
Memory Usage: 41.6 MB, less than **73.34%** of Java online submissions for Top K Frequent Elements.