0451. Sort Characters By Frequency¶
题目信息¶
- 题号:
0451
- 难度:
Medium
- 主题:
字符串、字符频次、降序排列、并列顺序
- 原题:
- 重点:
相同字符必须集中出现、频次高者排在前面、频次相同时顺序任意、大小写字符不同
题目重述¶
给定字符串 s,重新排列其中全部字符,使字符按照出现频次从高到低排列,并返回重排后的字符串。
每个字符实例必须恰好使用一次,同一种字符在结果中会连续出现。若多个字符的频次相同,它们之间可以采用任意顺序。s.length 位于 [1, 5 * 10^5],由大小写英文字母和数字组成;大小写视为不同字符。
自建示例¶
存在频次并列:
输入:s = "cccAAbb"
输出:"cccAAbb"
解释:c 出现 3 次,应排在最前;A 和 b 都出现 2 次,二者顺序可以交换,因此 cccbbAA 也合法。
所有字符频次相同:
输入:s = "2aB"
输出:任意由 "2"、"a"、"B" 各一次组成的排列
解释:三个字符频次均为 1,任何排列都满足降序频次要求。
统计频次后按块输出¶
结果只要求频次降序,并不要求同频字符的固定顺序,因此先统计每个字符出现次数,再把字符按照频次从高到低输出即可。字符总类数受输入字符集限制,题目中的大小写字母和数字可以直接用定长频次数组表示。
排序的是“字符种类”而不是每个字符实例;输出时一次追加该字符的完整频次,保证相同字符集中出现,同时避免对长度为 n 的字符串做逐字符比较排序。
C++ 实现¶
class Solution {
public:
std::string frequencySort(std::string s) {
std::array<int, 128> frequency{};
for (unsigned char c : s) ++frequency[c];
std::vector<std::pair<int, char>> groups;
for (int c = 0; c < 128; ++c) {
if (frequency[c] > 0) {
groups.push_back({frequency[c], static_cast<char>(c)});
}
}
std::sort(groups.begin(), groups.end(),
[](const auto& left, const auto& right) {
return left.first > right.first;
});
std::string result;
result.reserve(s.size());
for (const auto& [count, character] : groups) {
result.append(count, character);
}
return result;
}
};
代码分析¶
groups 中每个元素代表一种字符,比较器只按频次降序,频次相同时保持任意顺序即可满足题意。统计、排序字符种类和生成结果分别耗时 O(n)、O(c log c)、O(n),其中 c 是不同字符数;额外空间为 O(c+n),后者来自返回字符串。