本文介绍一种 o(n) 时间复杂度的算法，用于在整数数组中找出最长的“无聊前缀”（即删除一个元素后，剩余各数字出现次数完全相等的最长前缀），核心在于动态维护频次分布的关键统计量。
本文介绍一种 o(n) 时间复杂度的算法，用于在整数数组中找出最长的“无聊前缀”（即删除一个元素后，剩余各数字出现次数完全相等的最长前缀），核心在于动态维护频次分布的关键统计量。
所谓“无聊集合”（boring set），是指存在某个元素，将其移除后，集合中所有剩余元素的出现频次严格相等。本题要求：对给定数组 a[0..n-1]，找出最大的 l（2 ≤ l ≤ n），使得前缀 a[0..l-1] 是无聊的。
关键洞察在于：前缀 a[0..i] 是无聊的，当且仅当其频次分布满足以下三类情形之一（设当前最大频次为 maxFreq，频次为 maxFreq 的不同数字个数为 cntMax，频次为 maxFreq−1 的不同数字个数为 cntMaxMinus1，总不同数字个数为 distinct）：
-
情形 A：所有元素频次均为 1
→ maxFreq == 1，此时删去任意一个元素，其余仍全为 1 次（或空），合法。 -
情形 B：仅一个元素频次为 maxFreq，其余所有元素频次均为 maxFreq − 1
→ 删去那个高频元素的一次出现，则所有元素频次变为 maxFreq − 1，合法。
条件：cntMax == 1 && (maxFreq - 1) * (distinct - 1) + maxFreq == i + 1（总长度守恒），但更简洁的判定是：cntMax == 1 && cntMaxMinus1 == distinct - 1。 -
情形 C：所有元素频次均为 maxFreq，且恰好有一个元素频次为 1
→ 删去那个频次为 1 的元素，其余元素频次保持 maxFreq，合法。
条件：maxFreq > 1 && cntMax == distinct - 1 && cntOne == 1（其中 cntOne 是频次为 1 的元素个数）。
✅ 实际实现中，我们只需动态维护四个变量：
- freq[x]：数字 x 的当前出现次数（哈希表）
- cntFreq[f]：频次为 f 的不同数字个数（如 cntFreq[2] = 3 表示有 3 个数字当前出现了 2 次）
- maxFreq：当前最大频次
- distinct：当前不同数字个数
每次加入 a[i] 时：
- 先将 freq[a[i]] 从旧频次 f_old 更新为 f_new = f_old + 1
- 对应地：cntFreq[f_old]--，cntFreq[f_new]++
- 若 f_new > maxFreq，则 maxFreq = f_new
- 同时更新 distinct（首次出现时加 1）
然后检查上述三种情形是否成立。若成立，则更新答案 ans = i + 1。
以下是完整 Java 实现：
import java.util.*;
public class BoringPrefix {
public static int findLongestBoringPrefix(int[] arr) {
if (arr == null || arr.length < 2) return 0;
Map<Integer, Integer> freq = new HashMap<>(); // x -> count
Map<Integer, Integer> cntFreq = new HashMap<>(); // count -> number of distinct x with this count
int maxFreq = 0;
int distinct = 0;
int ans = 0;
for (int i = 0; i < arr.length; i++) {
int x = arr[i];
int oldCnt = freq.getOrDefault(x, 0);
int newCnt = oldCnt + 1;
// Update freq
freq.put(x, newCnt);
// Update cntFreq: decrement old count bucket
if (oldCnt > 0) {
cntFreq.put(oldCnt, cntFreq.get(oldCnt) - 1);
if (cntFreq.get(oldCnt) == 0) cntFreq.remove(oldCnt);
}
// Increment new count bucket
cntFreq.put(newCnt, cntFreq.getOrDefault(newCnt, 0) + 1);
// Update maxFreq and distinct
if (oldCnt == 0) distinct++;
if (newCnt > maxFreq) maxFreq = newCnt;
// Check boring condition
boolean isBoring = false;
// Case 1: all frequencies are 1
if (maxFreq == 1) {
isBoring = true;
}
// Case 2: one element has maxFreq, others have maxFreq-1
else if (cntFreq.getOrDefault(maxFreq, 0) == 1) {
int cntBelow = cntFreq.getOrDefault(maxFreq - 1, 0);
if (cntBelow == distinct - 1) {
isBoring = true;
}
}
// Case 3: all elements have maxFreq, except one with frequency 1
else if (cntFreq.getOrDefault(1, 0) == 1) {
if (cntFreq.getOrDefault(maxFreq, 0) == distinct - 1) {
isBoring = true;
}
}
if (isBoring) {
ans = i + 1; // prefix length = index + 1
}
}
return ans;
}
// Example usage
public static void main(String[] args) {
int[] arr = {1, 2, 3, 1, 2, 2, 3, 3, 3, 1, 4, 4, 5};
System.out.println(findLongestBoringPrefix(arr)); // Output: 10
}
}⚠️ 注意事项：
- 时间复杂度为 O(n)，空间复杂度为 O(独特元素个数)，远优于暴力枚举所有前缀并排序频次的 O(n² log n) 方法；
- cntFreq 映射中只保留非零频次项，避免冗余存储；
- 情形判断需覆盖全部逻辑分支，尤其注意 maxFreq == 1 与 maxFreq > 1 的分离处理；
- 示例输入中长度为 13 的数组，前 10 个元素 [1,2,3,1,2,2,3,3,3,1] 的频次为：1→3, 2→3, 3→3，但等等——实际统计得：1:3, 2:3, 3:3？不，重新计数：位置 0–9 共 10 个数：1,2,3,1,2,2,3,3,3,1 → 1:3, 2:3, 3:4。删去一个 3 后，1:3, 2:3, 3:3，满足情形 B（maxFreq=4, cntMax=1, cntMaxMinus1=2, distinct=3），验证通过。
该算法结构清晰、可扩展性强，适用于各类基于频次约束的子数组/前缀判定问题。
