题目大意：
最大相等频率
给出一个正整数数组 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^51 <= nums[i] <= 10^5
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1224
解题思路分析：
这道题是一道难题。难点不在于算法，而在于全程要保持逻辑高度清晰。不论做题时还是写这篇分析，我都觉得很难表述清楚自己的想法，因此本篇文章我尽量多用例子来解释说明。
题目要求得到的前缀数组减去一个元素后，剩下的部分中，每个数字出现的次数要相同。比如：
int[] nums =[1,2,1,3,2];
数组中有2个1，2个2，和1个3，如果把3删除掉，剩下的元素均只出现过2次，因此nums本身可以作为一个答案。
这道题的关键在于要弄清需要删掉的这个元素可以有哪些种情况，总结如下：
- 如果nums数组中只有一种元素时，那么整个数组的长度即是答案。解释：元素只有一种时，不存在与其他元素进行个数比较问题。
- 如果nums数组中存在多种元素，每种元素的个数都相同并且个数都为1时，那么整个数组的长度即是答案。解释：因为所有数的个数都是1，删除任何一个数后剩下的数字的个数仍然还是1。
- 如果nums数组中存在多种元素，每种元素的个数都相同并且个数都大于1时，不存在合理解。比如[1,1,2,2,3,3]，这时删除任何一个数字都不能保证剩下的元素个数相同。
- 如果nums数组中存在多种元素，每种元素的个数不同，并且个数种类大于2种时，不存在合理解。解释：存在三种及以上的个数时，我们无法通过删除一个数字来使得所有数的个数相同。比如[1,,2,2,3,3,3]
- 如果nums数组中存在多种元素，每种元素的个数不同，并且个数种类等于2种时，这时要看这两种个数的大小，如果想要找到合理解，必须保证其中一种个数为1，比如：[1,1,2,2,5]，长度为1的个数是1，删除一个5即可。还有一种情况，个数为1的那一种的长度比个数较多长度多1，也可以返回当前数组长度，比如：[1,1,2,2,5,5,5]，长度为1的个数是1，删除一个5即可。其他情况均无法找到合理解。比如：[1,1,1,2,2,2,5,5]，或者比如：[1,1,2,2,5,5,5,6,6,6]
解题时必须将以上的情况都考虑到，才能通过测试。笔者认为，这类题目在面试时应该不会经常问到，毕竟要考虑的情况太多，代码写起来也相对复杂，不利于短时间内判断出面试者的算法能力（纯个人观点）。
看下完整代码：
public int maxEqualFreq(int[] nums) {
int res = 0; // 返回结果
// 记录每种个数的数量
Map<Integer, Integer> countMap = new HashMap<>();
int[] numMap = new int[100001]; // 记录每个数字的个数
for (int num : nums) { // 循环每个数字
int numCount = ++numMap[num]; // 当前数字个数加一
// 更新此个数出现的次数（加一）
countMap.put(numCount, countMap.getOrDefault(numCount, 0) + 1);
// 如果该数字之前出现过，要将之前出现的次数减一。
// 比如数字1曾经出现过3个，出现过3个的数字个数为2
// 当前数字又是1，于是1变为出现了4个，这时应将出现过3个的数据减一
if(numCount-1>0){
// 如果加一之后的次数为0，直接删除该key
if (countMap.get(numCount-1)-1 == 0) {
countMap.remove(numCount - 1);
} else {
countMap.put(numCount-1, countMap.get(numCount-1)-1);
}
}
// 利用countMap查看当前是否存在合理解
res = Math.max(res, findMax(countMap));
}
return res;
}
// countMap的key为个数，value为该个数的数量
private int findMax(Map<Integer, Integer> countMap) {
Set<Integer> keySet = countMap.keySet();
// 如存在2种以上的个数，不存在合理解
if (keySet.size() > 2) {
return -1;
}
Iterator<Integer> it = keySet.iterator();
int key1 = it.next(); // 取得第一种个数
int value1 = countMap.get(key1); // 第一种个数的数量
if (keySet.size() == 1) { // 如果只存在一种个数
// 如果个数的数量为1（当前前缀数组所有数相同）
// 或者个数为1（当前前缀数组所有数都不同）
// 返回前缀数组长度。
// 否则返回-1
return value1==1 || key1 == 1 ? key1*value1 : -1;
}
// 以下为只存在2种个数
int key2 = it.next(); // 取得第二种个数
int value2 = countMap.get(key2); // 第二种个数的数量
// 如果其中一种个数的数量为1，并且该个数为1或者比另一个个数大一
if (value1 == 1 && (key1 == 1 || key1 - key2 == 1)
|| value2 == 1 && (key2 == 1 || key2 - key1 == 1)) {
// 返回当前前缀数组长度。
return key1 * value1 + key2 * value2;
}
return -1; // 剩余情况均为不合理解。
} 本题解法执行时间为75ms。
Runtime: 75 ms, faster than 44.47% of Java online submissions for Maximum Equal Frequency.
Memory Usage: 50.7 MB, less than 100.00% of Java online submissions for Maximum Equal Frequency.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1224-maximum-equal-frequency解题思路分析/