347. Top K Frequent Elements

我的方法是先用unordered_map 統計次數, 之後存到Vector進行排序

再取出排序後的前k個, 時間複雜度是O(nlogn)

class Solution {
public:
    static bool sortvec(pair<int, int> A, pair<int, int>B){
        return A.second < B.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> st;
        for(int i = 0;i < nums.size();i++){
            st[nums[i]]++;
        }
        vector<pair<int, int>> vec;
        for(auto s: st){
            vec.push_back({s.first, s.second});
        }
        sort(vec.rbegin(), vec.rend(), sortvec);
        vector<int> res ;
        for(int i = 0; i < k;i++){
            res.push_back(vec[i].first);
        }
        return res;
    }
};

但總覺得有更神的方法

一種是用min heap, 我只保存k個值, 多的話我就開始淘汰

時間複雜度為O(nlogk)

class Solution {
public:
    static bool sortvec(pair<int, int> A, pair<int, int>B){
        return A.second < B.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> st;
        for(int i = 0;i < nums.size();i++){
            st[nums[i]]++;
        }
        priority_queue<int, vector<int>, greater<int>> q;
        for(auto s: st){
            q.push(s.second);
            while(q.size() > k) q.pop();
        }
        vector<int> res;
        for(auto s:st){
            if(s.second >= q.top()){
                res.push_back(s.first);
            }
        }
        return res;
    }
};

最後一個是 Bucket sort

這個方法野蠻聰明的, 簡單來說就是把總數換成bucket, 然後依據頻率大小放入

然後從最大的頻率開始拿, 拿到res== k 就回傳

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> st;
        for(int i = 0;i < nums.size();i++){
            st[nums[i]]++;
        }
        vector<vector<int>> bk(nums.size() +1);
        for(auto s:st){
            bk[s.second].push_back(s.first);
        }
        reverse(bk.begin(), bk.end());
        vector<int> res;
        for(auto b: bk){
            for(auto f:b){
                res.push_back(f);
                if(res.size() == k) return res;
            }
        }
        return res;
    }
};