LEETCODE 1224. Maximum Equal Frequency解题思路分析

题目大意：

最大相等频率

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： 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解题思路分析/