https://leetcode.com/problems/sort-characters-by-frequency/?tab=Description
思路1： Priority Queue
- 先把所有字符的出现次数统计一下----O(n)
- 然后把 (字符, 出现次数) 做成一个node推入优先队列，按题目要求重载比较规则----O(n log n)
- 最后依次pop队列元素，构造结果----O(n)
Time complexity: O(n log n)
Space complexity: O(n)
struct Node {char c;int cnt;Node(char _c = '0', int _cnt = 0) : c(_c), cnt(_cnt) {}bool operator< (const Node &other) const {return this->cnt < other.cnt ||(this->cnt == other.cnt && this->c < other.c);} };class Solution { public:string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> hash_map;for (char c : s) {hash_map[c]++;}priority_queue<Node> q;string ret = "";for (char c : s) {q.push(Node(c, hash_map[c]));}while (!q.empty()) {ret.push_back(q.top().c);q.pop();}return ret;} };思路2：
其实大想法还是一样的，就是想办法把（出现次数，字符）按出现次数为首要比较准则构造出来，前面的方法是用Priority Queue / Max Heap。借用counting sort的思想，可以开一个存放字符的数组，如下：
| 1 | 2 | 3 | ... | n |
|---|---|---|---|---|
| 出现1次的字符 | 出现2次的字符 | 出现3次的字符 | ... | 出现n次的字符 |
统计好每个字符的出现次数后，就可以填这个表了，填好这个表之后，从后往前扫描一遍就能构造出结果了。有个问题须要注意，可能多个不同的字符出现的次数相等，所以这个表应该设计成存放字符串而不是单个字符的表。
Time complexity: O(n)
Space complexity: O(n) ---严格的O(n)
class Solution { public:string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> cnt;for (auto c : s) {cnt[c]++;}vector<string> charof(s.size() + 1);for (const auto& kv : cnt) {charof[kv.second].append(kv.second, kv.first);}string ret = "";for (int i = charof.size() - 1; i >= 1; --i) {if (!charof[i].empty()) {ret.append(charof[i]);}}return ret;} };个人认为这个方法其实并不多好，在字符串很长时会有较大的空间浪费，比如考虑一个极端情况：一个长度为100万+1的字符串只有两个字符构成："aaaaa...ab"，字符a出现了100万次，字符b出现了1次，这个表就只有第1和第(n-1)的位置放了东西，其他地方都浪费了，如果再算上构造结果的复杂度，在我看来时间是不止O(n)的...
所以在这种情况下，把数组换成Map / Tree Map是比较好的做法，可以有效避免空间浪费，且具有排序的功能（C++ std::map内部是一颗红黑树），最后构造结果的时候从map的最大key开始遍历就可以了：
string frequencySort(string s) {if (s.empty()) return "";unordered_map<char, int> cnt;for (auto c : s) {cnt[c]++;}map<int, string> charof;for (const auto& kv : cnt) {charof[kv.second].append(kv.second, kv.first);}string ret = "";for (auto it = charof.rbegin(); it != charof.rend(); ++it) {ret.append(it->second);}return ret; }map的插入是O(logn)，所以时间复杂度是O(n logn)，但是个人认为在字符串长度很长的情况下性能不比上面的做法差。