上一篇
Java求众数的最快方法是什么？
在Java中求众数（出现次数最多的元素），常用方法包括：，1. 使用HashMap统计元素频率，遍历找出最大值。，2. 先对数组排序，再线性扫描统计连续相同元素的最大频次。，3. 使用流处理结合Collectors.groupingBy进行分组计数。
方法1：HashMap统计频率（推荐）
原理：利用HashMap记录每个元素的出现次数，再遍历找出最大频率对应的元素。
时间复杂度：O(n)
空间复杂度：O(n)
方法2：排序后遍历
原理：先排序数组，再线性扫描统计连续相同元素的频率。
时间复杂度：O(n log n)（排序开销）
空间复杂度：O(1)（不考虑排序的栈空间）
import java.util.*; public class ModeFinder { public static List<Integer> findMode(int[] nums) { Arrays.sort(nums); List<Integer> modes = new ArrayList<>(); int currentCount = 1, maxCount = 1; // 遍历统计连续元素频率 for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { currentCount++; } else { currentCount = 1; } if (currentCount > maxCount) { maxCount = currentCount; modes.clear(); modes.add(nums[i]); } else if (currentCount == maxCount) { modes.add(nums[i]); } } return modes; } }
方法3：摩尔投票法（适用于唯一众数）
原理：通过抵消不同元素快速定位可能超过半数的众数，需二次验证。
时间复杂度：O(n)
空间复杂度：O(1)
public class ModeFinder { public static int findMajority(int[] nums) { int candidate = 0, count = 0; // 投票阶段 for (int num : nums) { if (count == 0) candidate = num; count += (num == candidate) ? 1 : -1; } // 验证是否超过半数 count = 0; for (int num : nums) { if (num == candidate) count++; } return (count > nums.length / 2) ? candidate : -1; // -1表示无绝对众数 } }
方法对比与选择建议
| 方法 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| HashMap | 通用场景，尤其数据量大且无序 | 高效稳定，支持多个众数 | 占用额外空间 |
| 排序遍历 | 数据量小或允许排序 | 空间复杂度低 | 排序耗时长 |
| 摩尔投票 | 明确存在唯一众数且占比超50% | 空间最优 | 不适用多个众数场景 |
关键注意事项
- 多个众数处理：前两种方法天然支持多个众数（如[1,1,2,2]返回[1,2]），摩尔投票法仅返回一个候选值。
- 空数组/边界值：代码需添加空数组检查（如if (nums.length == 0) return Collections.emptyList();）。
- 频率相同：当所有元素频率一致时，整个数组都是众数（如[4,5,6]返回[4,5,6]）。
实际应用场景
- 数据分析：统计用户行为中的高频事件。
- 信号处理：识别传感器数据中的常见值。
- 机器学习：处理分类任务中的高频标签。
引用说明：
本文代码示例参考Oracle官方HashMap文档及经典算法书籍《算法导论》，摩尔投票法实现基于Boyer-Moore多数投票算法（1981年提出）。
