1224 Maximum Equal Frequency 最大相当频率
Description:
Given an array nums of positive integers, return the longest possible length of an array prefix of nums, such that it is possible to remove exactly one element from this prefix so that every number that has appeared in it will have the same number of occurrences.
If after removing one element there are no remaining elements, it's still considered that every appeared number has the same number of ocurrences (0).
Example:
Example 1:
Input: nums = [2,2,1,1,5,3,3,5]
Output: 7
Explanation: For the subarray [2,2,1,1,5,3,3] of length 7, if we remove nums[4] = 5, we will get [2,2,1,1,3,3], so that each number will appear exactly twice.
Example 2:
Input: nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
Output: 13
Constraints:
2 <= nums.length <= 10^5
1 <= nums <= 10^5
标题形貌：
给你一个正整数数组 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 <= 10^5
1 <= nums <= 10^5
思绪：
模拟
用哈希表统计各个数字出现的次数
记录并更新出现次数的最大值和出现次数的最大值出现的次数
统共只有 3 种情况须要更新结果, 末了的 4 是可以撤除的
每个数字仅出现 1 次, 123456/1234564
数组中只有一种数字, 111111/1111114
每种数字出现次数雷同, 1112223334/1112223334444
当出现次数的最大值为 1, 分析数组中只有独特的 i 个值, 123456
当出现次数的最大值和出现次数的最大值出现的次数的乘积为 i, 分析数组中出现的值不须要删除, 有两种情况, 全为 1 个数字, 111111, 大概撤除一个数字之后每个数字出现的次数都是出现次数的最大值, 1111114/1112223334
当出现次数的最大值的出现次数为 1, 且出现次数的最大值为 i // d + 1, 分析出现次数的最大值出现的次数刚好比出现次数的第二大的值(可为0)多出了1, 删掉该值即可, 1234564/1112223334444
时间复杂度为 O(n), 空间复杂度为 O(1)
代码:
C++: |
