Boyer-Moore投票算法

算法简介

在一个数组中，存在一个众数，众数的数量要大于数组大小的一半。设计时间复杂度为 O(n)，空间复杂度为 O(n) 的算法: 在数组中找出该众数。

该算法维护了两个变量：候选人 candiate 和投票数目 count。其基本算法步骤如下：

1. 初始化 candiate 为任意值，count 的值为0；
2. 遍历数组，如果 count 为 0，那么将当前元素的值赋给 candiate；
3. 如果当前元素的值与 candiate 的值相同，则 count 加1；
4. 如果当前元素的值与 candiate 的值不同，则 count 减1；
5. 重复步骤 2-4，最终 candiate 即为目标众数；

简单来说，该算法的过程如下：

例如，现在要竞选总统，只有某人的票数超过总票数的一半时，这个人才会当选总统。目前的投票结果如下：

在前 4 票中，Mike 占了 2 票，Tina 和 John 分别占 1 票，没有人的票数大于 2 票，那么他们之间就会相互抵消：

在第 5 票和第 8 票中，同样的，Mike 占 2 票，John 和 Henry 分别占 1 票，没有人的票数大于 2 票，那么他们之间会相互抵消：

在最后剩下的 2 票中，只有 Mike，因此 Mike 最终竞选成功，当选总统:

正确性证明

假设当前数组大小为 \(n\)，众数的数目为 \(m\)，且一定存在 \(2m>n\)。

此时，如果抵消一对数组元素，且这两个元素中至少有一个数不是众数，那么会存在如下两种情况：

情况1：这两个元素都不是众数

该情况下存在 \(2m>n-2\)，该式子依然成立。

情况2：这两个元素有一个是众数

该情况下存在 \(2(m-1)>n-1\)，该式子依然成立。

算法实现

class Solution {
public:
	int majorityElement(vector<int>& nums) {
		int candidate = -1, int count = 0;
		for (int num : nums) {
			if (num == candidate)
				++count;
			else if (--count < 0) {
				candidate = num;
				count = 1;
			}
		}
		return candidate;
	}
};

题目来源：Leetcode - 169.多数元素