难度: 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运行时间: 48 ms
内存: 22.1 MB
class Solution:
def maxEqualFreq(self, nums: List[int]) -> int:
n = len(nums)
a = Counter(nums)
b = Counter(a.values())
k = n
if len(a.keys()) == 1:
return n
while k > 0:
if len(b) == 2:
if 1 in b and b[1] == 1:
return k
ma,mi = max(b.keys()),min(b.keys())
if b[ma] == 1 and (ma - mi) == 1:
return k
if len(b) == 1 and 1 in b:
return k
m = nums.pop()
l = a[m]
b[l] -= 1
if b[l] == 0:
del b[l]
if l > 1:
b[l-1] += 1
a[m] -= 1
k -= 1
return k
题解通过使用两个哈希表，一个记录每个数字的出现次数（哈希表a），另一个记录每个出现次数有多少个数字（哈希表b）。通过从后向前逐步检查数组，每次去掉一个元素并更新两个哈希表，尝试找到符合条件的最长前缀。具体检查条件包括：1. 哈希表b中只有两种出现频率时，其中一种频率为1且只有一个数字具有该频率，或者两种频率的数字个数相差1且只有一个数字具有更高的频率；2. 如果哈希表b中只有一种出现频率，且该频率为1，则也符合条件。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxEqualFreq(self, nums: List[int]) -> int:
n = len(nums) # 数组长度
a = Counter(nums) # 计数每个数字的出现次数
b = Counter(a.values()) # 计数每个出现次数有多少个数字
k = n # 初始化k为数组长度
if len(a.keys()) == 1:
return n # 如果只有一个数字，直接返回数组长度
while k > 0: # 从后向前遍历数组
if len(b) == 2: # b中有两种出现频率
if 1 in b and b[1] == 1:
return k # 条件1：一种频率为1且只有一个数字具有该频率
ma, mi = max(b.keys()), min(b.keys()) # 获取最大和最小频率
if b[ma] == 1 and (ma - mi) == 1:
return k # 条件2：最大频率比最小频率大1，且具有最大频率的数字只有一个
if len(b) == 1 and 1 in b:
return k # 条件3：只有一个频率且为1
m = nums.pop() # 移除数组最后一个元素
l = a[m] # 获取该元素的出现次数
b[l] -= 1 # 更新哈希表b
if b[l] == 0:
del b[l] # 如果某个频率的数字数量为0，删除这个频率
if l > 1:
b[l-1] += 1 # 减少的次数非1，更新哈希表b
a[m] -= 1 # 更新哈希表a
k -= 1 # 更新前缀长度
return k # 返回结果
从后向前检查数组可以更有效地确定何时删除一个数组元素能使剩余部分满足条件，从而找到最长的满足条件的前缀。这种方法让我们能从完整的数组开始逐步缩小问题规模，而从前向后会导致我们需要在每个步骤中重新评估整个数组的状态，这在算法上不是最优解决方式。而从后向前可以保持之前的状态，仅对当前检查的元素进行调整，使得算法更加高效。
在哈希表b中删除频率为0的项是为了保持哈希表b的准确性和高效性。如果不删除这些频率为0的项，哈希表b会逐渐增加不必要的条目，这会导致空间浪费和可能增加查找时间。通过及时删除这些无用的条目，算法可以保持较高的执行效率和较低的空间复杂度。
这种情况下，每个元素都只出现一次，即所有元素的频率相同。如果这是唯一的频率且为1，则删除任何一个元素后，剩余的元素都不存在于数组中，因此剩余数组为空或者仍然满足每个元素的频率为1。这是一个特殊情况，通常表示数组中的每个数字均唯一，移除任何元素都不会影响其他元素的频率。
使用`if len(b) == 2`来判断是否有两种出现频率是基于问题条件的简化。这种方法假设只有两种频率的情况是我们需要特别处理的情况，它可能不足以描述问题当存在多于两种频率时的复杂性。例如，如果有三种或更多种频率存在，这种方法可能无法正确判断是否可以通过删除一个元素使得剩余元素满足条件，因此可能需要更复杂的逻辑来处理更多种频率的情况。