摩尔投票法是java中查找数组众数的最优解，时间复杂度o(n)、空间复杂度o(1)，需两阶段：第一阶段遍历得候选者，第二阶段验证其出现次数是否超半数。
在 Java 中查找数组中出现次数超过一半的元素，最经典高效的方法是摩尔投票法（Boyer-Moore Majority Vote Algorithm），时间复杂度 O(n)，空间复杂度 O(1)，无需额外存储结构。
摩尔投票法：一次遍历找出候选者
该算法基于“抵消”思想：假设某个元素是众数（出现 > n/2 次），它与其他所有元素“一对一抵消”后仍会剩余。算法分两步：
- 第一阶段：遍历数组，维护一个候选元素 candidate 和计数 count；遇到相同元素 count++，不同则 count--；count 为 0 时更新 candidate
- 第二阶段：重新遍历数组，统计 candidate 实际出现次数，确认是否真超半数（防止无众数时误判）
Java 代码实现（含校验）
以下是一个完整、健壮的实现：
public static int findMajorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Array is empty");
}
// 第一阶段：找候选者
int candidate = nums[0];
int count = 1;
for (int i = 1; i nums.length / 2) {
return candidate;
} else {
throw new IllegalArgumentException("No majority element exists");
}
}
其他可行方法对比
虽然摩尔投票法最优，但了解替代方案有助于理解场景边界：
- 哈希表计数：用 HashMap 统计频次，再遍历找 > n/2 的 key；时间 O(n)，空间 O(n)，适合需同时查多个元素频次的场景
- 排序后取中位数：排序后索引 n/2 处的元素即为候选（若众数存在必在此位置）；时间 O(n log n)，空间 O(1)（原地排序），但无法验证是否存在
- 随机采样+验证：随机选元素并验证频次，期望时间 O(n)，但有小概率失败，一般不用于确定性要求高的场合
注意事项与边界情况
使用摩尔投票法时需留意：
- 算法只保证：若众数存在，一定能被选出；但不保证选出的一定是众数 —— 所以第二阶段验证不可省略
- 数组为空或长度为 1 时需单独处理；长度为 1 时该元素即为众数
- 输入含负数、零、重复值均不影响算法正确性
- 若题目允许返回“不存在”而非抛异常，可将最后逻辑改为 return occurrences > nums.length / 2 ? candidate : -1（需约定无效值）
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
