Concise C++ solution using STL sort


  • 19
    G
    class Solution {
    public:
        string frequencySort(string s) {
            int counts[256] = {0};
            for (char ch : s)
                ++counts[ch];
            sort(s.begin(), s.end(), [&](char a, char b) { 
                return counts[a] > counts[b] || (counts[a] == counts[b] && a < b); 
            });
            return s;
        }
    };
    

  • 0
    H

    That was awesome!


  • 2
    G

    Thanks. But I think it is not efficient. Just a brute force solution first came up.


  • 0
    K

    Concise. but I think the time complexity of the solution is O(n*log(n)). and not so efficient


  • 0

    nice solution


  • 0
    S

    Can someone explain these two lines I'm very confused

     [&](char a, char b) { 
                return counts[a] > counts[b] || (counts[a] == counts[b] && a < b);
    

    It's a comparator function but what does [&] mean?


  • 0
    G

    @saurabh3 [&] can be used to capture all automatic variables odr-used in the body of the lambda by reference and current object by reference if exists, which means counts is captured and we can directly use counts to compare.

    You can find more details here: http://en.cppreference.com/w/cpp/language/lambda


  • 0
    S

    @garygao1993 With an additional array index (0 to 255) to be sorted according to the frequency, the time complexity can be decreased to O(n) even if we use the sort method.

    class Solution {
    public:
        std::string frequencySort(std::string s) {
            int freq[256] = {0};
            int index[256] = {0};
            std::iota(std::begin(index), std::end(index), 0); // fill index 0 -> 255
            // O(n)
            for (auto c : s){
                freq[c]++;
            }
            // constant, since index is of fixed size 256
            std::sort(std::begin(index), std::end(index), 
                [&freq](int a, int b){return freq[a] > freq[b];}); // descending
            // O(n) since at last r will be of same size of s
            std::string r;
            for (int i = 0; i < 256; i++){
                int c = index[i]; // c's frequency is stored in freq[c]
                int f = freq[c];
                if (f == 0)
                    break;
                r.append(f, c);
            }
            return r;
        }
    };
    

  • 0

    @shuhua I have the same idea with you. :D And I got 9ms, beats 99.89% just now. Here is my code:

    class Solution {
    public:
        string frequencySort(string s)
        {
            string ans;
            pair<char, int> freq[256] = { {0, 0} };
            for (const auto &c : s) {
                freq[c].first = c;
                ++freq[c].second;
            }
            sort(begin(freq), end(freq),
                [](pair<char, int>& l, pair<char, int>& r) {
                return l.second > r.second;
            });
            for (auto it = begin(freq); it != end(freq); ++it)
                ans.append(it->second, it->first);
            return ans;
        }
    };
    

  • 0
    L

    I use the same method as you except that I use unordered_map to record the number of each characters.

    class Solution {
    public:
        string frequencySort(string s) {
        	if(s.size() == 0)	return "";
    
            unordered_map<char,int> map;
            for(auto c : s)
            	map[c]++;
            sort(s.begin(),s.end(),
            	[=](char a, char b){return map[a] > map[b];}
            	);
    		return s;
        }
    };
    };
    

    In lambda expression, if I capture local variable by value, i.e.

    sort(s.begin(),s.end(),
            	[=](char a, char b){return map[a] > map[b];}
            	);
    

    compiler shows error:

    passing ‘const std::unordered_map<char, int>’ as ‘this’ argument discards qualifiers [-fpermissive]
             sort(s.begin(),s.end(),[=](char a, char b){return map[a] > map[b];});
    

    However, if I capture by reference, i.e.

    sort(s.begin(),s.end(),
            	[&](char a, char b){return map[a] > map[b];}
            	);
    

    it works.

    Could anyone please tell my why I cannot capture by value?

    Thanks


Log in to reply
 

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