『Leetcode 5225』最大相等频率

『题目』：

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

• 从前缀中 删除一个 元素后，使得所剩下的每个数字的出现次数相同。

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

『限制条件』：

2 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

『输入输出』

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

输入：nums = [1,1,1,2,2,2]
输出：5

输入：nums = [10,2,8,9,3,8,1,5,2,3,7,6]
输出：8

『题解』（技巧）：

这道题有小技巧，首先定义一个数组pin用来统计频率出现的次数，数组count用来统计每个数字出现的频率，那么能出现合法的前缀莫过于三种情况：

1. [2,2,2,1,1,3,3]、[1,1,1,1,1...]，也就是最大频率pin[max]出现1次，次小频率pin[max-1]出现无数次，这时候最大频率-1，就可以合法。
2. [1,2,3,4,5...]，也就是pin[1]出现无数次，随便删1个数即可。
3. [1,2,2,2,3,3,3]，也就是pin[max]出现无数次，然后pin[1]只出现1次，删除那个频率为1的数即可。

『实现』：

public class test23 {

    public int maxEqualFreq(int[] nums) {

        int ans = 0;
        if(nums == null || nums.length == 0) return 0;
        int length = nums.length;
        int[] pin = new int[length + 5];
        int[] count = new int[length + 5];

        for(int i = 0; i <= length;i++)
        {
            pin[i] = 0;
            count[i] = 0;
        }

        int max = 0;
        for(int i = 0; i < length;i++)
        {
            int x = nums[i];
            count[x]++;

            if(count[x] > 1)
            {
                pin[count[x] - 1] --;
                pin[count[x]] ++;
            }
            else pin[count[x]]++;

            max = Math.max(max,count[x]);

            int now = i + 1;

            if(pin[1] == 1 && pin[max] * max + 1== now)
            {
                ans = now;
            }
            else if(pin[max] == 1 && max + pin[max - 1]*(max - 1) == now )
            {
                ans = now;
            }
            else if(max == 1)
            {
                ans = now;
            }
        }

        return ans;
    }

    public static void main(String[] args) {

        test23 of = new test23();
        int[] nums = {1,1,1,2,2,2,3,3,3,4,4,4,5};
        System.out.println(of.maxEqualFreq(nums));
    }
}