题目描述
给出一个正整数数组 nums
,请你帮忙从该数组中找出 最长 前缀,满足从前缀中 删除一个 元素后,使得所剩下的每个数字的出现次数相同。
如果删除这个元素后没有剩余元素存在,仍可认为每个数字都具有相同的出现次数(也就是 0 次)。
样例
输入: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],里面每个数字都出现了两次。
输入:nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出:13
输入:nums = [1,1,1,2,2,2]
输出:5
输入:nums = [10,2,8,9,3,8,1,5,2,3,7,6]
输出:8
限制
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
算法
(频次统计,找规律) $O(n)$
对于前缀数字出现的频次,观察可以发现以下三种前缀可以满足条件:
1, 1, 1, ..., 1, 1
1, k, k, ..., k, k
k, k, ..., k, k + 1
可以在遍历前缀的过程中,记录每个数字的频次 cnt
,以及这个频次出现的次数 freq
,和最大的频次是 max_f
。
如果 max_f == 1
或 max_f * freq[max_f] + 1 == length
或 (max_f - 1) * (freq[max_f - 1] + 1) + 1 == length
,则更新 ans = length
。
时间复杂度
- 仅遍历一次数组,每次常数时间更新上述变量,故时间复杂度为 $O(n)$。
空间复杂度
- 哈希表存放 $n$ 个数字以及对应的频率,故需要额外 $O(n)$ 的空间。
C++ 代码
class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
int n = nums.size(), ans = 0;
unordered_map<int, int> cnt, freq;
int max_f = 0;
for (int i = 0; i < n; i++) {
if (cnt[nums[i]] > 0)
freq[cnt[nums[i]]]--;
cnt[nums[i]]++;
freq[cnt[nums[i]]]++;
max_f = max(max_f, cnt[nums[i]]);
if (max_f == 1 || max_f * freq[max_f] + 1 == i + 1
|| (max_f - 1) * (freq[max_f - 1] + 1) + 1 == i + 1)
ans = i + 1;
}
return ans;
}
};
太强了,看了题解都理解了20分钟
cnt 和 freq可以用数组表示么
可以
这个好啊
点赞
太强了
前面第三种情况 (max_f - 1) * freq[max_f - 1] + 1 == length 写错了吧,和代码不一样。写成(max_freq - 1) * freq[max_freq - 1] + max_freq == i + 1
确实
请问这句话是什么意思,为什么还要自减呢
对于nums = [1,1,1,2,2,2],在遍历到1,1时会出现fre[1]=1,fre[2]=1的情况。因此每次遍历到的数字如果之前存在的话就要自减,防止一个数字既出现k次又出现k+1次
cnt记录每一种数字的出现次数、freq记录每种出现次数的出现次数;当一个数字出现多次,cnt会增加,它在freq里原来对应的次数-1,改变成新的次数+1
# 赞,解释的豁然开朗
NB
顶级理解,tql
前面说明里面的 (max_f - 1) * freq[max_f - 1] + 1 == length 是不是应该写成
(max_f - 1) * (freq[max_f - 1] + 1) + 1 == length 看代码里面好像是这个样子
## 是的 原文写错了
(max_f - 1) * freq[max_f - 1] + 1 == length
请问这个是在什么情况下需要加这个判断?
在罗列的三种条件中有写