困难

问题描述

给你一个正整数数组 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 <= 105
• 1 <= nums[i] <= 105

分类讨论

需要求最长前缀的长度，因此需要数组进行一次遍历，在遍历过程中，对各个数的个数、最大频率和最大频率的次数进行记录，每一个数遍历结束后，需要对当前得到的前缀进行判断是否存在最大前缀的可能：

• 当记录到的最大频率 $maxCnt = 1$，删除任意一个数都满足题目要求，最大前缀长度为当前遍历到的长度。
• 当记录到的最大频率 $macCnt$ 与 最大频率的次数 $maxCntCnt$，它们的乘积 $macCnt \times maxCntCnt$ 为当前遍历到的长度减 $1$，删除多出的数即可满足题目要求，最大前缀长度为当前遍历到的长度。
• 当记录到的最大频率的次数 $maxCntCnt = 1$，其余数出现的频率次数为 $maxCntCnt - 1$，那么删除一个出现最大的数即可满足题目要求，最大前缀长度为当前遍历到的长度。

注：因为$maxCntCnt = 1$，若减去一个出现最多的数后算出各个数平均出现的频率是 $maxCntCnt = 1$，那么各个数出现的频率只能是 $maxCntCnt = 1$

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxEqualFreq = function (nums) {
  const cnts = new Map()
  let maxCnt = 0
  let maxCntCnt = 0
  let ans = 0
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    if (!cnts.has(num)) {
      cnts.set(num, 1)
    } else {
      cnts.set(num, cnts.get(num) + 1)
    }
    if (maxCnt < cnts.get(num)) {
      maxCnt = cnts.get(num)
      maxCntCnt = 1
    } else if (maxCnt === cnts.get(num)) {
      maxCntCnt++
    }
    if (maxCnt === 1 || maxCnt * maxCntCnt === i || (maxCntCnt === 1 && i / cnts.size === maxCnt - 1)) {
      ans = i + 1
    }
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$