原文链接: https://leetcode-cn.com/problems/maximum-equal-frequency

英文原文

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：

输入：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

通过代码

高赞题解

[WeeklyContest 158 Q1 分割平衡字符串]C++
[WeeklyContest 158 Q2 可以攻击国王的皇后]C++ 迭代
[WeeklyContest 158 Q3 掷骰子模拟]C++ 动态规划
[WeeklyContest 158 Q4 最大相等频率]C++ 分类讨论

事后总结：这种题目需要分类讨论，找出所有满足答案得情况再动手。直接分析写代码导致遇到特殊情况乱改代码。

问题分析：
能够满足答案的条件:
1、只有一种数字。如：1 1 1 1 1 
2、有多种数字，但每个数组只出现一次。 如：1 2 3 4 5
3、有多种数字，其中一种数字出现n+1次，其他出现n次。如：1 1 1 2 2 3 3 4 4
4、有多种数字，其中一种数字出现1次，其他出现n次。如：1 2 2 2 3 3 3 4 4 4
两个数组，arr_a 和 arr_b, arr_a[i]表示数字i出现次数，arr_b[i]表示出现频率为i的数字个数。
因此，成立条件为，arr_b[1]==n || 最高频次==1
                || (arr_b[最高频次]==1 && arr_b[最高频次-1]==(n-1))
                || (arr_b[最高频次]==(n-1) && arr_b[1]==1)
由此，又需要维护两个变量，n: 一共有多少种数字，ma: 最高频次为多少

class Solution {
    int arr_a[100005], arr_b[100005];
public:
    int maxEqualFreq(vector<int>& nums) {
        int n = 0, ma = 0, ans = 0;
        memset(arr_a, 0, sizeof(arr_a));
        memset(arr_b, 0, sizeof(arr_b));
        for(int i = 0; i < nums.size(); i++){
            int cur = nums[i];
            if(arr_a[cur]==0) n++;
            arr_a[cur]++;
            ma = max(ma, arr_a[cur]);
            arr_b[arr_a[cur]]++;
            if(arr_a[cur]>1) arr_b[arr_a[cur]-1]--;

            if(ma==1 || arr_b[1]==n || (arr_b[ma]==1 && arr_b[ma-1]==(n-1))|| (arr_b[ma]==(n-1) && arr_b[1]==1)){
                ans = i+1;
            }
        }
        return ans;
    }
};

统计信息

通过次数	提交次数	AC比率
4839	14711	32.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言