算法:投票法
改进的投票法（Boyer-Moore Voting Algorithm）是一种非常高效的算法，用于在一个数组中找到出现次数超过一半的数字。它利用了“多数票”的性质，通过抵消的方式找到候选数字，并验证其是否满足条件。
改进的投票法（Boyer-Moore Voting Algorithm）
核心思想
- 多数票性质：如果一个数字出现次数超过数组长度的一半，那么在抵消其他数字后，这个数字仍然会剩余。
- 两轮操作：
- 第一轮投票：找到一个候选数字（可能的“多数票”）。
- 第二轮验证：验证这个候选数字是否真的出现次数超过一半。
详细步骤
- 第一轮投票：
- 初始化一个候选数字 candidate 和计数器 count。
- 遍历数组：
- 如果当前数字等于候选数字，计数器加1。
- 如果不等于候选数字，计数器减1。
- 如果计数器变为0，更换候选数字为当前数字，并重置计数器为1。
- 第一轮结束后，candidate 是可能的“多数票”。
- 第二轮验证：
- 遍历数组，统计候选数字的出现次数。
- 如果出现次数超过数组长度的一半，返回该数字；否则返回0。
class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {if (numbers.empty()) {return 0; // 如果数组为空，直接返回0}// 第一轮投票：找到候选数字int candidate = numbers[0];int count = 1;for (int i = 1; i < numbers.size(); ++i) {if (numbers[i] == candidate) {++count; // 如果当前数字等于候选数字，计数器加1} else {--count; // 如果不等于候选数字，计数器减1if (count == 0) {candidate = numbers[i]; // 更换候选数字count = 1; // 重置计数器}}}// 第二轮验证：确认候选数字是否符合条件//在确认存在的情况下无需第二遍遍历count = 0; // 重置计数器for (int num : numbers) {if (num == candidate) {++count; // 统计候选数字的出现次数}}// 如果候选数字的出现次数超过数组长度的一半，返回该数字；否则返回0return (count > numbers.size() / 2) ? candidate : 0;//这里0表示未找到值}
};
代码解释
- 第一轮投票：
- 初始化 candidate 和 count，假设第一个数字是候选数字。
- 遍历数组：
- 如果当前数字等于候选数字，说明它是一个“支持票”，计数器加1。
- 如果当前数字不等于候选数字，说明它是一个“反对票”，计数器减1。
- 如果计数器变为0，说明当前候选数字被“抵消”了，更换候选数字为当前数字，并重置计数器为1。
- 第二轮验证：
- 第一轮投票结束后，candidate 是可能的“多数票”，但不一定满足条件。
- 遍历数组，统计 candidate 的出现次数。
- 如果出现次数超过数组长度的一半，返回 candidate；否则返回0。
为什么这种方法有效？
- 多数票性质：如果一个数字出现次数超过一半，那么在抵消过程中，它最终会剩余。
- 两轮操作：第一轮投票找到候选数字，第二轮验证确保结果的正确性。
时间复杂度和空间复杂度
时间复杂度：O(n)。两轮遍历数组，每轮都是线性时间。
空间复杂度：O(1)。只使用了常数级别的额外空间。
这种方法是解决“多数票问题”的最优解，既高效又简洁。