LeetCode算法日记：1224. 最大相等频率

1224. 最大相等频率

日期：2022/8/18

题目描述：给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：

从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。
如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

示例：

输入：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]，里面每个数字都出现了两次。

输入：nums = [1,1,1,2,2,2,3,3,3,4,4,4,5]
输出：13
1
2
3
4
5
6

思路：

用哈希表
times存储每个元素出现多少次，element存储出现该次数的元素个数，即element[n]=出现了n次的元素的个数
用res存储要return的数，maxTimes代表最多次数
遍历nums,每次都更新times,element

更新res的时候，nums[0]到目前为止要满足下列条件的其中一条：
1.所有元素的出现次数都为1，这时随便删除一个元素都满足要求
2.只有一个元素出现次数为1，其他出现次数都为maxLength
3.只有一个元素出现次数为maxLength-1，其他出现次数都是maxLength
1
2
3
4
5
6
7
8
9

代码+解析：

class Solution {
public:
    int maxEqualFreq(vector& nums) {
        unordered_map times,element;
        int res=0, maxTimes=0;
        int size = nums.size();
        for(int i=0; i 1) element[times[n]-1]--; //假如n出现了2次，那么出现1次的元素中就要删去n，即减去1
            maxTimes = max(maxTimes, times[n]); //如果times[n]大于当前最大出现次数，则变化

            if(maxTimes == 1) res = len;
            if(maxTimes * element[maxTimes] + 1 == len) res = len;
            if((maxTimes-1) * (element[maxTimes-1] + 1) + 1 == len) res = len;
        }
        return res;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22