本文共 1310 字，大约阅读时间需要 4 分钟。

给出一个正整数数组 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

示例 3：

输入：nums = [1,1,1,2,2,2]输出：5

示例 4：

输入：nums = [10,2,8,9,3,8,1,5,2,3,7,6]输出：8

提示：

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

解题思路

首先遍历nums中元素，对于当前遍历到的元素cur，我们有两种选择：删或者不删。

**删：**前面的数出现频率相同。

**不删：**前面的数大部分（除了一个）和当前的数频率相同，其中一个数出现1次或者出现f+1（假设当前数的频率是f）。

对于第一种情况如何判断？我们需要知道当前数的频率f，并且还要知道有k个数的频率是f，那么f*k应该等于n（n表示当前遍历到的元素个数）。第二种情况呢？采用相同思路。

class Solution:    def maxEqualFreq(self, nums: List[int]) -> int:        f, n = collections.defaultdict(int), len(nums)        k, res = [0] * (n + 1), 0        for i in range(1, n+1):            a = nums[i-1]            k[f[a]] -= 1            f[a] += 1            k[f[a]] += 1            t = f[a]            if k[t] * t == i and i < n:                res = i + 1            else:                d = i - k[t] * t                if d in [t + 1, 1] and k[d] == 1:                    res = i        return res

reference:

https://leetcode.com/problems/maximum-equal-frequency/discuss/403743/JavaC%2B%2BPython-Only-2-Cases%3A-Delete-it-or-not

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/102554671 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！