LeetCode 451. 根据字符出现频率排序
题目描述
题意分析
将字符串中的字符重新排列，使出现次数较多的字符块排在前面，同一种字符的所有出现必须放在一起。每种字符的数量与输入保持一致，不能去重或补入其他字符。
输入包含大小写英文字母和数字，大小写需要分别统计。同频字符的先后顺序任意，因此答案可能不唯一；本题要求按频次排序，不要求字典序。
解法：频次统计后排序不同字符
核心思路
[!blue]
最终结果由若干同字符块组成，每个块的长度就是该字符的频次。因此先统计
count[ch]，再只对出现过的不同字符排序，就能决定这些块的输出顺序，无需对原字符串的每一个位置排序。比较两个字符时，频次大的应排在前面。Java 比较器交换计数的比较方向，Go 使用
count[chars[i]] > count[chars[j]]。两者频次相同无需额外规则，任一先后关系都满足题意。排序完成后，对每种字符连续输出
count[ch]次。这样保证同字符集中、各字符数量不变，而且整个结果的字符块频次非递增，正好满足全部要求。输入字符都在 ASCII 范围内，可以用长度为 128 的数组直接计数。
解题步骤
- 遍历字符串，将每个字符对应的计数加一。
- 收集计数大于零的字符，得到不同字符列表。
- 按计数从大到小排序该列表，同频顺序任意。
- 依次取出列表中的字符，每次连续追加它的全部出现次数。
- 返回构造出的字符串。
代码实现
class Solution {
public String frequencySort(String s) {
int[] count = new int[128];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
}
List<Character> chars = new ArrayList<>();
for (char ch = 0; ch < count.length; ch++) {
if (count[ch] > 0) {
chars.add(ch);
}
}
// 只排序不同字符，频次高的字符块优先输出。
chars.sort((first, second) -> Integer.compare(count[second], count[first]));
StringBuilder result = new StringBuilder(s.length());
for (char ch : chars) {
// 完整写出每次出现，不能只输出去重后的字符。
result.append(String.valueOf(ch).repeat(count[ch]));
}
return result.toString();
}
}
import "sort"
func frequencySort(s string) string {
count := [128]int{}
for i := 0; i < len(s); i++ {
count[s[i]]++
}
chars := make([]byte, 0, 62)
for ch, frequency := range count {
if frequency > 0 {
chars = append(chars, byte(ch))
}
}
// 只排序不同字符，频次高的字符块优先输出。
sort.Slice(chars, func(i int, j int) bool {
return count[chars[i]] > count[chars[j]]
})
result := make([]byte, 0, len(s))
for _, ch := range chars {
// 完整写出每次出现，不能只输出去重后的字符。
for times := count[ch]; times > 0; times-- {
result = append(result, ch)
}
}
return string(result)
}
复杂度分析
- 时间复杂度：$O(n+k\log k)$，其中 $n$ 是字符串长度，$k$ 是不同字符数。统计和输出各为 $O(n)$，只对 $k$ 种字符排序；本题 $k\le62$。
- 空间复杂度：$O(n+k)$，包含构造结果的缓冲区和不同字符列表，固定计数数组为常数空间。
关键点总结
[!green]
- 先统计再按字符块排序，把排序规模从出现次数降为不同字符数。
- 输出时按完整频次展开，确保结果长度和每种字符的数量不变。
- 同频不要求唯一顺序，比较器无需额外按字典序排序。
易错点总结
[!yellow]
- 比较器方向写反会得到频次升序，与题目要求相反。
- 只输出不同字符而没有按频次重复，会错误地把输入去重。
- 只统计 26 个小写字母或合并大小写，会改变输入字符的构成。
- Go 的字符列表应创建为长度零的切片再追加；预设非零长度会把零值字节也当成待排序字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 347. 前 K 个高频元素 | 中等 | 同样先按值统计频次，原题只选前k种，本题按频次输出全部字符并保留重数。 |
| 692. 前K个高频单词 | 中等 | 同样按频次排序，原题单词同频时有字典序规则，本题同频字符通常可任意排序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！