-
Notifications
You must be signed in to change notification settings - Fork 7
/
SortCharactersByFrequency.cpp
42 lines (36 loc) · 995 Bytes
/
SortCharactersByFrequency.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// Problem: https://leetcode.com/problems/sort-characters-by-frequency/
#include<priority_queue>
#include<string>
#include<unordered_map>
using namespace std;
struct CharCount {
CharCount(char c, int count) : ch(c), count (count) {}
char ch;
int count;
};
struct compareCharCount {
inline bool operator()(const CharCount& l, const CharCount& r) {
return l.count < r.count;
}
};
class SortCharactersByFrequency {
public:
string frequencySort(string s) {
string out = "";
priority_queue<CharCount, vector<CharCount>, compareCharCount> p_queue;
unordered_map<char, int> char_count_map;
for (int index = 0; index < s.size(); ++index) {
char_count_map[s[index]]++;
}
unordered_map<char, int>::iterator it;
for (it = char_count_map.begin(); it != char_count_map.end(); ++it) {
p_queue.push(CharCount(it->first, it->second));
}
while (not p_queue.empty()) {
CharCount cc = p_queue.top();
p_queue.pop();
out.append(cc.count, cc.ch);
}
return out;
}
};