入门力扣自学笔记127 C++ （题目编号1224）

1224. 最大相等频率

题目：

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

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-equal-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

在遍历nums时统计每种频次出现的个数。设当前遍历的下标为i。
例如：
[2,2,1,1,5,3,3,5]， 在遍历到下标为5时，2出现了2次，1出现了2次，5出现了1次，3出现了1次。
所以频次为2的有2个，频次为1的有2个。

显然当频次的种类超过两种是不合法的。

当只有一种频次时，合法情况：

频次为1的个数有i+1个。
频次为i+1的有1个。

当有两种频次时，合法情况：

两种频次相差为1且较大的频次只有1个。
频次为1的有1个。

---

代码：

class Solution {
public:
    int mp[100005];
    int maxEqualFreq(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        map<int,int> cnt;
        for (int i=0; i
            if (cnt.count(mp[nums[i]]) && --cnt[mp[nums[i]]] == 0) {
                cnt.erase(mp[nums[i]]);
            }
            mp[nums[i]]++;
            cnt[mp[nums[i]]]++;
            int ok = 0;
            if (cnt.size() == 1) {
                if (cnt.begin()->first == 1 && cnt.begin()->second == i+1) ok = 1;
                if (cnt.begin()->first == i+1 && cnt.begin()->second == 1) ok = 1;
            } else if (cnt.size() == 2) {
                if (cnt.begin()->first+1 == cnt.rbegin()->first && cnt.rbegin()->second == 1) ok = 1;
                if (cnt.begin()->first == 1 && cnt.begin()->second == 1) ok = 1;
            }
            if (ok) ans = i+1;
        }
        return ans;
    }
};