Shared 3 C++ solutions: 2 by std::sorts, 1 by priority queue(12~93ms)


  • 1

    The first one delivers the answer in nlog(n) time. It is very simple, by sorting the input string according to frequency and break ties using the numerical comparison. (in 93 ms)

        string frequencySort(string s) {
            int buf[256] = {};
            int* cnts = buf+128;
            for(char ch : s) ++cnts[ch];
            sort(s.begin(),s.end(),
                [cnts] (char c1, char c2) -> bool {
                    return (cnts[c1] == cnts[c2]) ? (c1 < c2) : (cnts[c1] > cnts[c2]);
                }
            );
            return s;
        }
    

    The second one is in linear time: Record the presence of any character, sort them by frequency, and reconstruct the string. (in 13ms)

        string frequencySort(string s) {
            int buf[256] = {};
            int* cnts = buf+128;
            string presence;
            for(char ch : s) if(++cnts[ch] == 1) presence += ch;
            sort(presence.begin(),presence.end(),
                [&cnts] (char c1, char c2) -> bool {
                    return cnts[c1] > cnts[c2];
                }
            );
            s.clear();
            for(char ch : presence) {
                s.append(cnts[ch],ch);
            }
            return s;
        }
    

    Based on the previous solution we can push further by using priority queue because we only need extreme values for each iteration. (in 12ms)

        string frequencySort(string s) {
            int buf[256] = {};
            int* cnts = buf+128;
            string presence;
            for(char ch : s) if(++cnts[ch] == 1) presence += ch;
    
            auto pred = 
                [cnts] (char c1, char c2) -> bool {
                    return cnts[c1] < cnts[c2];
                };
            s.clear();
            make_heap(presence.begin(),presence.end(), pred);
            while(presence.empty() == false) {
                char ch = presence[0];
                s.append(cnts[ch],ch);
                pop_heap(presence.begin(), presence.end(), pred);
                presence.pop_back();
            }
            return s;
        }
    

Log in to reply
 

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