C++ using unordered_map and priority queue very easy for beginners 46ms


  • 3
    K

    '''

      string frequencySort(string s) {
        unordered_map<char, int> m1;
    priority_queue<pair<int, char>> q1;
     for (int i = 0;i<s.length();i++) {
    	m1[s[i]]++;
      }
    
    for (auto it = m1.begin();it != m1.end();it++) {
    	q1.push(make_pair(it->second, it->first));
    }
    string res = "";
    while (q1.size()) {
    	pair<int , char> y1 = q1.top();
    	for(int i=0;i<q1.top().first;i++)
    	    res += q1.top().second;
    	q1.pop();
    }
    return res;
    } 
    

    '''


  • 0
    R
    This post is deleted!

  • 0
    I
    This post is deleted!

  • 1

    Thanks for share. And this solution could run faster by modifying some code.
    Here is my code with priority_queue, it runs 9ms:

    class Solution {
    public:
        string frequencySort(string s)
        {
            string ans;
            int freq[256] = { 0 };
            priority_queue<pair<int, char>> pq;
            for (const auto &c : s) ++freq[c];
            for (int i = 0; i < 256; ++i) {
                if (freq[i])
                    pq.push(make_pair(freq[i], i));
            }
            while (!pq.empty()) {
                ans.append(pq.top().first, pq.top().second);
                pq.pop();
            }
            return ans;
        }
    };
    

Log in to reply
 

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