C++ straight up bucket sort (19ms)


  • 0
    M

    I think the O(N) space management cost for the buckets complicates this more than the in-place sorting solutions.

        string frequencySort(string s) {
            auto N = static_cast<int>(s.size());
    
            // Count frequencies
            int freq[256] = { 0 };
            for (auto ch : s)
                freq[ch]++;
    
            // Distribute in buckets
            vector<string> buckets(N + 1);
            for (int i = 0; i < 256; ++i)
                if(freq[i] != 0)
                    buckets[N - freq[i]] += char(i);
    
            // Accumulate result
            string res;
            for (auto item : buckets)
                for (auto ch : item)
                    res.append(freq[ch], ch);
    
            return res;
        }
    

    Here's an example of in-place sort, just O(1) extra space:

        string frequencySort(string s) {
            int freq[256] = { 0 };
            for (auto ch : s)
                freq[ch]++;
    
            auto cmp = [&](char lhs, char rhs) {
                if (freq[lhs] == freq[rhs])
                    return lhs > rhs;
    
                return freq[lhs] > freq[rhs];
            };
    
            sort(begin(s), end(s), cmp);
            return s;
        }
    

Log in to reply
 

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