来一道和「字节跳动」相关的题目。
题目描述
平台：LeetCode
题号：1224
给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：
- 从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。
示例 1：
代码语言：javascript复制输入：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：
代码语言：javascript复制输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
提示：
模拟（计数 分情况讨论）
我们使用 cnt 数组记录每个数的出现次数（即 cnt[i] = x 含义为数值 i 的出现次数为 x 次），以及使用 sum 来记录出现次数为某个值的数有多少个（即 sum[i] = x 含义为出现次数为 i 的数值共有 x 个），同时使用 max 来记录最大出现次数
。
从前往后处理 nums，假设当前处理到的数值为
（前缀所含数量为
）有如下几种情况，我们可以更新最大长度 ans：
：说明当前处理到的所有
均只出现了一次，此时任意删除一个均满足要求；
：说明有一个数值单独出现了一次（其余出现次数为 max 的数值 被删除的一个数 = 总数量
），删除后即满足要求；
：说明出现次数为 max 的数值只有一个，其余出现次数均为 max - 1，对其删除一次后即满足要求（删除该出现次数为 max 的数值后，会导致出现次数为 max - 1 的数值多一个，此时有「出现次数为 max - 1 的数值 被删除的一个数 = 总数量
」）。
Java 代码：
代码语言：javascript复制class Solution {
static int[] cnt = new int[100010], sum = new int[100010];
public int maxEqualFreq(int[] nums) {
Arrays.fill(cnt, 0); Arrays.fill(sum, 0);
int n = nums.length, max = 0, ans = 0;
for (int i = 0; i < n; i ) {
int t = nums[i], cur = cnt[t], len = i 1;
sum[cur] ; sum[cur - 1]--;
max = Math.max(max, cur);
if (max == 1) ans = len;
if (max * sum[max] 1 == len) ans = len;
if ((max - 1) * (sum[max - 1] 1) 1 == len) ans = len;
}
return ans;
}
}
C 代码：
代码语言：javascript复制class Solution {
public:
int maxEqualFreq(vector<int>& nums) {
vector<int> cnt(100010, 0), sumv(100010, 0);
int n = nums.size(), maxv = 0, ans = 0;
for (int i = 0; i < n; i ) {
int t = nums[i], cur = cnt[t], len = i 1;
sumv[cur] ; sumv[cur - 1]--;
maxv = max(maxv, cur);
if (maxv == 1) ans = len;
if (maxv * sumv[maxv] 1 == len) ans = len;
if ((maxv - 1) * (sumv[maxv - 1] 1) 1 == len) ans = len;
}
return ans;
}
};
Python 代码：
代码语言：javascript复制class Solution:
def maxEqualFreq(self, nums: List[int]) -> int:
cnt, sumv = [0] * 100010, [0] * 100010
n, maxv, ans = len(nums), 0, 0
for i, t in enumerate(nums):
cur, lenv = cnt[nums[i]] 1, i 1
cnt[t] = 1
sumv[cur] = 1
sumv[cur - 1] -= 1
maxv = max(maxv, cur)
if maxv == 1: ans = lenv
if maxv * sumv[maxv] 1 == lenv: ans = lenv
if (maxv - 1) * (sumv[maxv - 1] 1) 1 == lenv: ans = lenv
return ans
TypeScript 代码：
代码语言：javascript复制function maxEqualFreq(nums: number[]): number {
let n = nums.length, max = 0, ans = 0
const cnt = new Array<number>(100010).fill(0), sum = new Array<number>(100010).fill(0)
for (let i = 0; i < n; i ) {
let t = nums[i], len = i 1, cur = cnt[t]
sum[cur] ; sum[cur - 1]--;
max = Math.max(max, cur)
if (max == 1) ans = len
if (max * sum[max] 1 == len) ans = len
if ((max - 1) * (sum[max - 1] 1) 1 == len) ans = len
}
return ans
};
- 时间复杂度：
- 空间复杂度：
