投票算法可找出出现次数超过n/2的主元素，核心是抵消：相同+1、不同-1、归零换候选；需二次验证candidate实际频次是否>n/2，否则可能误判。
Java 中用投票算法（Boyer-Moore Majority Vote Algorithm）找出现次数超过一半的主元素，核心是“抵消”思想：相同数计数加一，不同数计数减一，归零后换候选。它时间 O(n)、空间 O(1)，无需哈希表。
投票算法原理与关键步骤
主元素定义为在长度为 n 的数组中出现次数 > n/2 的元素——这意味着它一定存在（题目保证时），且其“票数”一定能扛住所有其他元素的抵消。
- 初始化 candidate = 数组首元素，count = 1
- 从第二个元素开始遍历：若当前元素等于 candidate，则 count++；否则 count--
- 当 count 减到 0 时，用当前元素替换 candidate，并重置 count = 1
- 遍历结束后，candidate 是唯一可能的主元素（但需验证）
为什么必须二次验证？
投票算法只保证：如果主元素存在，它一定会成为最终 candidate；但它不保证 candidate 一定是主元素（比如 [1,2,3] 中算法也可能返回 3，但实际无主元素）。所以必须再遍历一次，统计 candidate 实际出现次数是否 > n/2。
- 验证不可省略，尤其题目未声明“主元素一定存在”时
- 验证过程只需一次额外遍历，不影响整体 O(n) 时间复杂度
完整 Java 实现（含验证）
// 示例：int[] nums = {2, 2, 1, 1, 1, 2, 2}; → 返回 2
public static int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) throw new IllegalArgumentException("数组为空");
// 第一阶段：投票选出候选者
int candidate = nums[0], count = 1;
for (int i = 1; i
if (count == 0) {
candidate = nums[i];
count = 1;
} else if (nums[i] == candidate) {
count++;
} else {
count--;
}
}
// 第二阶段：验证 candidate 是否真为主元素
int votes = 0;
for (int num : nums) {
if (num == candidate) votes++;
}
if (votes > nums.length / 2) return candidate;
throw new IllegalArgumentException("不存在主元素");
}
常见误区提醒
- 误以为 count 归零时直接跳过当前元素——应立即用它作为新 candidate
- 混淆“超过一半”和“不少于一半”：n=5 时需 >2.5 → 至少 3 次；n=4 时需 >2 → 至少 3 次
- 对空数组或单元素数组未做边界判断，导致索引越界或逻辑错误
- 使用 Integer 包装类参与比较（如 nums[i].equals(candidate)）引发 NullPointerException，应坚持基本类型 int
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
