求满足"无聊集"条件的最长数组前缀长度

若数字集合{x₁, x₂, ..., xₖ}可通过移除一个元素，使集合内每个数字的出现次数完全相同，则称其为"无聊集"。

给定长度为n的数组a₁,a₂,...,aₙ，需找出最大的l（2≤l≤n），使得长度为l的数组前缀是"无聊集"。

示例1：
输入：13，数组[1,2,3,1,2,2,3,3,3,1,4,4,5]
输出：10

你提供的代码仅能处理所有元素出现次数均为1的场景，逻辑完全不符合"无聊集"的定义：

• 代码通过滑动窗口维护所有元素出现次数为1的区间，最后返回l+1，但无聊集允许两种合法场景：要么某元素仅出现1次，其余元素出现次数相同；要么某元素出现次数比其他元素多1次，其余元素次数一致——你的代码完全没覆盖这些核心场景。

要判断一个前缀是否为无聊集，我们需要统计前缀中各元素的出现次数，再分析次数的分布：

1. 用两个映射分别记录：
   • 每个数字的出现次数（numCount）
   • 每种出现次数对应的数字数量（freqCount，比如有3个数字都出现了2次，那么freqCount中键2对应的值为3）
2. 满足以下任意一种情况，该前缀即为无聊集：
   • 所有数字出现次数完全相同（移除任意一个元素即可）
   • 仅存在一个数字出现1次，其余数字出现次数相同（移除这个仅出现1次的数字）
   • 仅存在一个数字的出现次数比其他数字多1，其余数字出现次数相同（移除该数字的一个实例）

我们遍历数组的每个前缀，逐步更新两个映射，每次检查是否满足上述条件，记录最大的符合要求的l。

import java.util.HashMap;
import java.util.Map;

public class BoringSetSolution {
    public static int findMaxLength(int[] arr) {
        // 记录每个数字的出现次数
        Map<Integer, Integer> numCount = new HashMap<>();
        // 记录「出现次数」的频率：key是次数，value是有多少个数字出现了该次数
        Map<Integer, Integer> freqCount = new HashMap<>();
        int maxL = 0;

        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            // 更新当前数字的出现次数
            int oldCount = numCount.getOrDefault(num, 0);
            if (oldCount > 0) {
                // 旧次数的频率减1，减到0则移除该键
                freqCount.put(oldCount, freqCount.get(oldCount) - 1);
                if (freqCount.get(oldCount) == 0) {
                    freqCount.remove(oldCount);
                }
            }
            int newCount = oldCount + 1;
            numCount.put(num, newCount);
            // 更新新次数的频率
            freqCount.put(newCount, freqCount.getOrDefault(newCount, 0) + 1);

            // 检查当前前缀是否为无聊集，更新最大长度
            if (isBoringSet(freqCount)) {
                maxL = i + 1;
            }
        }
        // 题目要求l≥2，若没有符合条件的前缀（理论上至少l=2可能符合），返回最小合法值2
        return maxL >= 2 ? maxL : 2;
    }

    private static boolean isBoringSet(Map<Integer, Integer> freqCount) {
        if (freqCount.size() == 1) {
            // 所有数字出现次数一致，满足条件
            return true;
        } else if (freqCount.size() == 2) {
            Integer[] freqs = freqCount.keySet().toArray(new Integer[0]);
            int f1 = freqs[0], f2 = freqs[1];
            int cnt1 = freqCount.get(f1), cnt2 = freqCount.get(f2);

            // 场景1：某数字仅出现1次，其余数字次数一致
            if ((f1 == 1 && cnt1 == 1) || (f2 == 1 && cnt2 == 1)) {
                return true;
            }
            // 场景2：某数字次数比其他多1，其余数字次数一致
            if ((f1 == f2 + 1 && cnt1 == 1) || (f2 == f1 + 1 && cnt2 == 1)) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,1,2,2,3,3,3,1,4,4,5};
        System.out.println(findMaxLength(arr)); // 输出10，匹配示例
    }
}

• numCount：实时跟踪当前前缀中每个数字的出现次数
• freqCount：实时统计每种出现次数对应的数字数量，简化后续的条件判断
• 每次遍历新元素时，先更新旧次数的频率，再更新新次数的频率，最后调用isBoringSet验证当前前缀是否合法
• isBoringSet方法严格按照我们梳理的合法场景进行判断，逻辑清晰且高效

内容的提问来源于stack exchange，提问作者biojaba