C++ solution with priority queue


  • 0
    L

    I first use a hash map to collect the frequency, then build a priority queue in descending order based on frequency. Then final output is easy to reconstruct.

    class wordWithFreq {
    public:
        char val;
        int freq;
        wordWithFreq(char c, int k)
        {
            val = c;
            freq = k;
        }
    };
    
    class wordWithFreq_compare {
    public:
        bool operator() (wordWithFreq& w1, wordWithFreq& w2) {
            return w1.freq < w2.freq;
        }
    };
    
    class Solution {
    public:
        string frequencySort(string s) {
            if(s.length() == 0) return s;
            // Step 1: get the frequency
            unordered_map<char, int> myMap;
            for(auto ss : s)
                myMap[ss] ++;
                
            // Step 2: build up the priority queue
            priority_queue<wordWithFreq,vector<wordWithFreq>,wordWithFreq_compare> myQueue;
            for(auto item : myMap)
            {
                wordWithFreq* t = new wordWithFreq(item.first, item.second);
                myQueue.push(*t);
            }
    
            // Step 3; reconstruct the string
            s.clear();
            while(!myQueue.empty())
            {
                wordWithFreq item = myQueue.top();
                myQueue.pop();
                for(int i = 0; i < item.freq; i ++)
                    s += item.val;
            }
            return s;
        }
    };

Log in to reply
 

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