Java数组O(n)众数计数器实现方法

本文介绍了一种基于计数数组的高效众数求解方法，专为Java中值域集中、可控的整型数组设计：通过一次遍历确定范围、二次遍历统计频次、三次遍历定位最大频次，实现严格O(n)时间复杂度，规避排序的O(n log n)开销和HashMap的哈希计算与扩容成本；方法天然支持负数偏移处理与多众数收集，并在缓存友好性、无装箱操作上优势显著——当你面对非负整数、小范围或已知区间（如[-50, 50]）的数据时，这可能是比通用方案更轻快、更确定的最优解。

在 Java 中，若数组元素范围已知且较集中（如非负整数、取值在 [0, k] 之间），可借助计数数组（count array）在 O(n) 时间内找出众数（出现次数最多的元素）。该方法本质是空间换时间，避免排序或哈希表的常数开销，适合整型数组且值域可控的场景。

适用前提：明确值域范围

计数数组法要求能预估数组中元素的最小值和最大值。最常见的是元素为非负整数且最大值不超过某个合理上限（例如 ≤ 10⁵）。若值域过大（如 int 范围全量）或含负数/浮点数，则需先离散化或改用 HashMap。

• 若所有元素 ∈ [min, max]，则申请长度为 max - min + 1 的 int 数组
• 遍历原数组时，将每个元素 x 映射到索引 x - min 处进行累加
• 最后扫描计数数组，找到最大计数值对应的索引，再还原为原始值

核心实现步骤（含边界处理）

以非负整数为例（min = 0），假设输入数组为 int[] nums：

• 先遍历一次，获取最大值 maxVal，确定计数数组长度：new int[maxVal + 1]
• 第二次遍历 nums，对每个 num 执行：count[num]++
• 第三次遍历 count 数组，记录最大频次及其下标：if (count[i] > maxCount) { maxCount = count[i]; mode = i; }
• 返回 mode 即为众数（若多个元素并列最多，此法默认返回值最小的那个；如需全部众数，可额外收集）

处理负数与多众数的扩展方式

若数组含负数，例如范围在 [-50, 50]，可统一偏移：令 offset = 50，则索引映射为 num + offset，计数数组长度为 101。若需返回所有众数，不提前终止，而是在第三步中维护一个 List，每当 count[i] == maxCount 时加入，遇到更大值则清空并更新。

对比其他方法的取舍

排序法（O(n log n)）或 HashMap（平均 O(n)，但有哈希计算与扩容开销）更通用；而计数数组法在满足值域约束时，真正严格线性、无装箱、缓存友好。实际编码中，建议先校验数据分布——若最大值远超数组长度（如 [0, 10⁶] 中仅 100 个数），空间浪费大，此时 HashMap 更稳妥。

今天关于《Java数组O(n)众数计数器实现方法》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！