LeetCode451 Sort Characters By Frequency

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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

样例

Example 1:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
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.Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

思路

将字符串按字符出现频率排序。

每个字符丢到对应的桶中,然后按桶的大小排序,最后按序输出即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
string frequencySort(string s) {
pair<int, char> p[128];
for (int i = 0; i < 128; ++i) p[i].first = 0, p[i].second = i;
for (char& c: s) p[c].first++;
sort(p, p+128);
string ans;
for (int i = 127; i >= 0; --i) while (p[i].first-->0) ans += char(p[i].second);
return ans;
}
};
分享到 评论