# LeetCode451. Sort Characters By Frequency（模拟）

## LeetCode451. Sort Characters By Frequency（模拟）

• Medium
• Accepted：81,281
• Submissions：148,685

Given a string, sort it in decreasing order based on the frequency of characters.

### Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

### Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

### Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

### 链接

https://leetcode.com/problems/sort-characters-by-frequency/

### 题解

• 对字符按照出现次数用sort进行排序，时间复杂度$O(nlogn)$
• 对字符进行“计数排序”，灵活使用vector，将出现次数相同的字符放到一起，再从后往前遍历

### 代码

• Runtime: 48 ms, faster than 30.00% of C++ online submissions for Sort Characters By Frequency.
• Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
• 话说直接写cmp函数会报错（已发现错误：reference to non-static member function must be called
class Solution {
public:
//    int cnt[256] = {0};
//
//    bool cmp(char a, char b)
//    {
//        return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
//    }

string frequencySort(string s) {
int n = s.length();
int cnt[256] = {0};
for (int i = 0; i < n; ++i)
cnt[s[i]]++;
// sort(s.begin(), s.end(), cmp); // error
sort(s.begin(), s.end(), [&](char a, char b) // 高级写法
{
return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
});
return s;
}
};
• Runtime: 28 ms, faster than 42.31% of C++ online submissions for Sort Characters By Frequency.
• Memory Usage: 18.6 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
class Solution {
public:
string frequencySort(string s) {
int n = s.length();
unordered_map <char, int> umap;
vector <string> vt(n + 1, "");
string ans;
for (int i = 0; i < n; ++i) // 统计字符出现次数
umap[s[i]]++;
unordered_map <char, int> ::iterator it;
for (it = umap.begin(); it != umap.end(); ++it) // 次数相同的放到一起
vt[it->second].append(it->second, it->first);
for (int i = n; i > 0; --i) // 从后往前遍历
{
if (!vt[i].empty())
ans.append(vt[i]);
}
return ans;
}
};

The end.
2019年2月15日 星期五