347. Top K Frequent Elements

1.問題

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

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