> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/347.-top-k-frequent-elements.md).

# 347. Top K Frequent Elements

## 1.問題

* 給予一個整數序列, 回傳前k個出現次數最多的成員

![](/files/-LItoDORB99CcoUq93Ek)

## 2.想法

* Bucket sort
  * 先計算每個數字出現的次數並推到無序容器, ex: unordered\_map中
  * 以次數為索引, 將(索引, 數字)推入有序器如vector中, 考慮相同出現次數的情況, 這邊可以用vector\<vector\<int>>
  * 將排在後面的成員推入回傳的序列中

## 3.程式碼

```
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if (nums.size() == 1)
        {
            return nums;
        }

        //Count
        unordered_map<int, int> cnts;
        for (auto num: nums) {
            cnts[num]++;
        }
        
        //Push into buckets
        vector<vector<int>> bucket(nums.size() + 1);
        for (auto cnt : cnts) {
            bucket[cnt.second].push_back(cnt.first);
        }
        
        //Push the higher index into res
        vector<int> res;
        int index = 0;
        for (int i = bucket.size() - 1 ; i >= 0; i--) {
            if (bucket[i].size() != 0 && index < k)
            {
                for (auto v: bucket[i]) {
                    index++;
                    res.push_back(v);
                }
            }
        }
        return res;
    }
};
```

## 4.Performance

![](/files/-LItoY8qslzZT60NFVdD)