Concise C++ average O(n) bucket Sort Solution


  • 2
    Z

    class Solution {
    public:

    string frequencySort(string s) {
        unordered_map<char, int> dict;
        vector<vector<char>> buckets(s.size() + 1);
        for(char c : s) 
            ++dict[c];
        for(auto p : dict) {
            buckets[p.second].push_back(p.first);
        }
        string res;
        for(int i = s.size(); i > 0; i--) {
            for(int j = 0; j < buckets[i].size(); j++) {
                int num = i;
                while(num--) {
                    res += buckets[i][j];
                }
            }
        }
        return res;
    }
    

    };


Log in to reply
 

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