【2022-08-18每日一题】1224. 最大相等频率
2022-08-18
1分钟阅读时长
2022-08-18每日一题：1224. 最大相等频率
- 难度：Hard
- 标签：数组 、 哈希表
给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：
- 从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。
示例 1：
输入：nums = [2,2,1,1,5,3,3,5] 输出：7 解释：对于长度为 7 的子数组 [2,2,1,1,5,3,3]，如果我们从中删去 nums[4] = 5，就可以得到 [2,2,1,1,3,3]，里面每个数字都出现了两次。
示例 2：
输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5] 输出：13
提示：
2 <= nums.length <= 1051 <= nums[i] <= 105
func maxEqualFreq(nums []int) (ans int) {
// count 存放数字的个数
// freq 记录出现次数为 f 的数的数目为 freq[f]
// maxFreq 记录最大的数字频率
count, freq, maxFreq := map[int]int{}, map[int]int{}, 0
for i, num := range nums {
if count[num] > 0 {
freq[count[num]]--
}
count[num]++
maxFreq = max(maxFreq, count[num])
freq[count[num]]++
// 三种情况：
// 1、所有数的频率都是1，如：[1,2,3,4,5] 去掉任意一个数都满足条件
// 2、去掉一个数后其他数的频率相等，如[44,44,55,55,33]去掉一个33
// 3、去掉一个数后包含当前数的所有数频率相等，如[21,21,11,11,31,31,31]去掉一个31
if maxFreq == 1 ||
maxFreq * freq[maxFreq] == i ||
maxFreq + (maxFreq - 1) * freq[maxFreq-1] == i + 1 {
ans = max(ans, i+1)
}
}
return ans
}
func max(a, b int) int {
if a < b {
return b
}
return a
}