class Solution {
public:
string frequencySort(string s) {
// Calculate frequency
unordered_map<char, int> freqMap;
for(auto &c: s) {
freqMap[c]++;
}
// Push into max heap
priority_queue<pair<char,int>, vector<pair<char,int>>, comp> maxHeap;
for(auto& p: freqMap) {
maxHeap.push(p);
}
// Build result string
string res;
while(!maxHeap.empty()) {
for(int i = 0; i < maxHeap.top().second; ++i) {
res += maxHeap.top().first;
}
maxHeap.pop();
}
return res;
}
private:
struct comp {
bool operator() (const pair<char,int>& p1, const pair<char,int>& p2) {
return p1.second < p2.second;
}
};
};
解法二 - 先把各字母的 freq 算出來,根據 freq 排序
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;
}
};