把所有在 s 中出现次数相同的字母归为一类：对于某个整数 k，出现恰好 k 次的字母构成一组。
我们要找出那一组字母，其成员（不同字母）数量比其它任何组都多。
将该组里的所有字母串成一个返回值字符串，字母顺序不限。
如果存在两个或多个组成员数相同且并列最多，则取出现次数 k 较大的那一组。
1
s 只包含小写英文字母。
输入: s = "aaabbbccdddde"。
输出: "ab"。
解释:
频率 (k)
组中不同字符
组大小
是否众数?
4
{d}
1
否
3
{a, b}
2
是
2
{c}
1
否
1
{e}
1
否
字符 'a' 和 'b' 的频率相同，都为 3，它们在众数频率组中。
题目来自力扣3692。
解题思路分析
题目要求：根据字符出现的频率对字母进行分组，找出成员数量最多的那一组（如果存在并列最多，则选择频率 k 较大的组），并将该组的所有字母拼接成字符串返回。
以输入 s = "aaabbbccdddde" 为例，详细步骤如下：
第一步：统计每个字母的出现次数
• 遍历字符串 "aaabbbccdddde"，统计每个小写字母出现的次数：
a: 3 次
b: 3 次
c: 2 次
d: 4 次
e: 1 次
第二步：按频率分组
• 将出现次数相同的字母归为一组，用哈希表存储，key 为频率 k，value 为该频率下的字母列表：
频率 4: {d}（1 个字母）
频率 3: {a, b}（2 个字母）
频率 2: {c}（1 个字母）
频率 1: {e}（1 个字母）
第三步：找出成员最多的组
• 比较每组中的字母数量：
频率 4 组：1 个字母
频率 3 组：2 个字母
频率 2 组：1 个字母
频率 1 组：1 个字母
• 频率 3 组的成员数量最多（2 个），因此它是候选组。
第四步：处理并列情况
• 假设有两个组的成员数量相同且都是最多，则选择频率 k 较大的组。
• 本例中没有并列情况，直接选择频率 3 组。
第五步：输出结果
• 将频率 3 组的字母列表 [a, b] 拼接成字符串 "ab"（字母顺序不限）。
最终输出
ab
复杂度分析
时间复杂度
• 统计字母频率：遍历一次字符串，长度为 n，时间复杂度 O(n)
• 分组和找最大组：遍历 26 个字母的计数数组，进行哈希表操作和比较，时间复杂度 O(26) ≈ O(1)
• 总时间复杂度：O(n) + O(1) = O(n)，其中 n 为字符串长度
额外空间复杂度
• 计数数组：固定大小 26，O(1)
• 分组哈希表：最多存储 26 个不同频率的组，每个组存储字母列表，总字母数不超过 26，所以空间 O(26) ≈ O(1)
• 总额外空间复杂度：O(1)（常数空间）
Go完整代码如下：
package main
import (
"fmt"
)
func majorityFrequencyGroup(s string)string {
cnt := [26]int{}
for _, b := range s {
cnt[b-'a']++
}
groups := map[int][]byte{}
mx := 0
for i, c := range cnt {
if c == 0 {
continue
}
groups[c] = append(groups[c], 'a'+byte(i))
iflen(groups[c]) > len(groups[mx])
配资网提示：文章来自网络，不代表本站观点。
