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