Two ways of bucket sort with c++


  • 0
    E

    Algorithm 1 O(nlgn)

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>hash;
        vector<int>res;
        for(auto n:nums)hash[n]++;
        multimap<int,int,greater<int> >bucket;
        for(auto p:hash)bucket.insert(pair<int,int>(p.second,p.first));
        for(auto p:bucket){
            res.push_back(p.second);k--;
            if(!k)break;
        }
        return res;
    }
    

    Algorithm 2 O(n)

    vector<int> topKFrequent(vector<int>& nums, int k){
        unordered_map<int,int>hash;
        vector<int>res;
        int m=0;
        for(auto n:nums){hash[n]++;if(hash[n]>m)m=hash[n];}
        vector<vector<int> >bucket(m+1,vector<int>{});
        for(auto p:hash)bucket[p.second].push_back(p.first);
        for(int i=m;i>=1;i--){
            for(auto n:bucket[i]){
                res.push_back(n);k--;if(!k)return res;
            }
        }
        return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.