[LeetCode] 1224. Maximum Equal Frequency

[grandyang]

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 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

Example 3:

Input: nums = [1,1,1,2,2,2]
Output: 5

Example 4:

Input: nums = [10,2,8,9,3,8,1,5,2,3,7,6]
Output: 8

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 105

这道题给了一个正整数数组 nums，让返回最长的前缀子数组的长度，使得移除一个元素后所有的数字的出现次数均相等，然后特别说明了假如移除数字后数组为空，也可以看作是所有数字出现次数为0，也是符合题意的。这样就可以知道返回结果最小也是1，因为给定的数组不会为空，还有一点需要特别注意，也就是题目中加粗的部分，必须要删除一个数字，不能不删除，也不能删除超过一个的数字。既然是跟数字出现次数有关，则肯定需要统计每个数字出现的次数（感觉像废话），这种题目做的多了去了，用一个 HashMap 来统计每个数字出现的次数就行了。这道题的难点就在于分析在哪些情况下删除一个数字后，剩下所有的数字的出现次数均相等，首先来说一种极端情况，就是数组中的每个数字都不相同，这样的话删掉任意一个数字后，剩下的所有数字还是各不相同，但同时也满足所有数字出现的次数均相同，均为1次，这样返回的结果就是 n-1 了。

然后再来看还有什么情况，比如移除一个单个的数字后，其余的数字出现次数均相同，且多于1次，就是例子2中的情况，如何快速判断这种情况呢？我们不仅需要知道每个数字出现的次数，而且还需要知道出现某个次数的不同数字有多少个，即反向映射，建立频率和具有该频率的数字的总个数之间的映射。这样只要知道最大的频率是多少，同时通过上面的映射也能迅速的知道具有该频率的数字有多少个，二者相乘得到的数字若正好等于某个前缀子数组的长度减1（因为需要删除一个数字），则表明就是例子2的情况。统计最大频率的好处就是，当其为1时，就知道数组中的每个数字都不相同了，就是最开始说的那种情况。再来想想还有没有漏掉的情况，是有的，但是题目中的例子没有给出，比如 [1, 1, 2, 2, 3, 3, 3]，这种情况是说最大频率的数字只有一个（是数字3），其余的所有数字的频率都是最大频率减1（数字1和2的频率都是2），这样的话只要去掉一个最大频率的数字就满足要求了，这种情况如何快速验证呢，就是用最大频率减1，再乘以该减1后的频率的数字的个数加1（因为之前的最大频率的数字减1后增加了当前频率的数字个数），若正好等于某个前缀子数组的长度减1就行了。

分析到这，基本上这道题应该没啥问题了吧，用两个 HashMap，分别建立数字和其出现次数的映射，还有频率和具有该频率的数字的个数的映射。然后就是遍历数组了，取出当前数字 num，还有其之前的频率 cnt，然后将 numCnt 中的映射值自增1，并更新最大频率 mx。由于数字 num 的频率从 cnt 变为 cnt+1 了，所以之前的频率 cnt 的映射个数应该自减1，为了严谨一些，判断一下 cnt 的映射值是否大于0，是的话再减1。然后 cnt+1 的映射值自增1，接下里就可以判断上面分析到的三种情况了，第一种就直接判断 mx 是否为1，第二种用 mx 乘以 freq[mx]，看是否等于i，第三种用 mx-1 乘以 feq[mx-1]+1，看是否等于i，只要满足上述任何一种情况，结果 res 就可以更新为 i+1，参见代码如下：

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        int res = 0, mx = 0, n = nums.size();
        unordered_map<int, int> numCnt;
        unordered_map<int, int> freq;
        for (int i = 0; i < n; ++i) {
            int num = nums[i], cnt = numCnt[num];
            mx = max(mx, ++numCnt[num]);
            if (freq[cnt] > 0) --freq[cnt];
            ++freq[cnt + 1];
            if (mx * freq[mx] == i || (mx - 1) * (freq[mx - 1] + 1) == i || mx == 1) {
                res = i + 1;
            }
        }
        return res;
    }
};

Github 同步地址:

#1224

参考资料：

https://leetcode.com/problems/maximum-equal-frequency/

https://leetcode.com/problems/maximum-equal-frequency/discuss/403743/JavaC%2B%2BPython-Only-2-Cases%3A-Delete-it-or-not

https://leetcode.com/problems/maximum-equal-frequency/discuss/403628/Easy-Python-Solution-Concise-10-lines-Explained-O(N)

LeetCode All in One 题目讲解汇总(持续更新中...)