###### tags: `Leetcode` `medium` `heap` `bucket` `sort` `python` `c++` `Top 100 Liked Questions`

# 347. Top K Frequent Elements

## [題目連結:] https://leetcode.com/problems/top-k-frequent-elements/description/

## 題目:
Given an integer array ```nums``` and an integer ```k```, return the ```k``` most frequent elements. You may return the answer in **any order**.
* k is in the range [1, the number of unique elements in the array].
* It is guaranteed that the answer is unique.

**Follow up:** Your algorithm's time complexity must be better than ```O(n log n)```, where n is the array's size.

**Example 1:**

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

**Example 2:**

Input: nums = [1], k = 1
Output: [1]

## 解題想法:
* 此題為求數組中k個最常出現的數字

* Sol1: O(NlogN)
* 使用hash table+ heap:
* 統計每個數字其出現次數，再存於heap
* python: heapq為min_heap
* c++: priority_queue<>為max_heap

## Python_Sol1: heap

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dic=defaultdict(int)
        que=[]
        for val in nums:
            dic[val]+=1
        for key in dic:
            heappush(que,(-dic[key],key))
        res=[]
        for i in range(k):
            res.append(heappop(que)[1])
        return res

## C++_Sol1: heap

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> dic;
        priority_queue<pair<int, int>> que;
        for (auto val: nums){
            dic[val]+=1;
        }
        //key: item.first
        //val: item.second
        for (auto &item: dic){
            pair<int,int> tmp(item.second, item.first);
            que.push(tmp);
        }
        vector<int> res;
        for (int i=0; i<k; i++){
            res.push_back(que.top().second);
            que.pop();
        }
        return res;
    }
};

* Sol2: **O(N)**
* 使用**Bucket Sort**
* Step1:
* 編號0~len(nums)個箱子 第i個箱子容量為i
* bucket=[ [] for _ in range(len(nums)+1)]
* Step2:
* hash table紀錄每個數字出現次數
* key: 數字
* val: 出現次數
* Step3:
* **對於hash table中每個key，將其val對應至bucket[val]**
* Step4:
* 將bucket中的元素存於res並取出k個

## Python_Sol2: Bucket Sort

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        #bucket sort!!! O(n)
        dic=defaultdict(int)
        #編號0~len(nums)個箱子 第i個箱子容量為i
        bucket=[ [] for _ in range(len(nums)+1)]
        for val in nums:
            dic[val]+=1
        for key in dic:
            #ex: key為1時 dic[1]=3 所以在bucket[3]放入1這個key
            bucket[dic[key]].append(key)
        res=[]
        for i in range(len(bucket)):
            if bucket[i]:
                res.extend(bucket[i])
        #因為res為由小到大,所以取最後k個
        return res[len(res)-k:]

## C++_Sol2: Bucket Sort
* 對於bucket:也可以用map< int,vector < int > >查詢較快

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> dic;
        int n=nums.size();
        vector<vector<int>> bucket(n+1, vector<int>());
        for (auto val: nums){
            dic[val]+=1;
        }
        for (auto& item: dic){
            bucket[item.second].push_back(item.first);
        }
        vector<int> res;
        for (int i=n; i>=0; i--){
            for (int j=0; j<bucket[i].size(); j++){
                res.push_back(bucket[i][j]);
                if (res.size()==k)
                    return res;
            }
        }
        return res;
    } 
};