C++ solution with priority_queue, beat 99% submission


  • 0
    F

    Idea is quite simple, build frequency count and revise 'char-count pair' and push to a priority queue. Last step is dequeue and build the return string.

    class Solution {
    public:
        string frequencySort(string s) {
            // frequency count
        	vector<int> hash(256, 0);
        	for(auto ch : s) {
        		++hash[ch];
        	}
            // build a customized queue
        	priority_queue<pair<int, char>, vector<pair<int, char> >, Compare> que;
            // reverse pair and push it to queue
        	for(int i = 0; i < 256; ++i) {
        		if(hash[i] > 0) {
        			que.push(make_pair(hash[i], (char)i));
        		}
        	}
        	string ans(s.length(), 0);
        	int index = -1;
            // dequeue and build the return string
        	while(!que.empty()) {
        		auto &t = que.top();
        		for(int i = 0; i < t.first; ++i) {
        			ans[++index] = t.second;
        		}
        		que.pop();
        	}
        	return ans;
    	}
    private:
    	class Compare {
    	public:
    		bool operator() (
    			const pair<int, char>& left, const pair<int, char>& right) const {
    	    	return left.first < right.first;
    	  	}
    	};
    };
    

Log in to reply
 

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