问题描述
$2013$年$408$统考中的一道数据结构题：若长度为$n$的数组$A$中有某个元素的个数$c$满足$c>(int)n/2$，则称该元素是主元素。查找一个数组是否有主元素和主元素的值的方法固然有许多：排序后计数，哈希表计数，计数排序等。但在评分标准中写着，要拿到该题的满分，需要实现一个时间复杂度为$O(n)$且空间复杂度为$O(1)$的算法，也就是本文要介绍的$Boyer-Moore$投票算法。
在$LeetCode$中有一道类似的算法题:$\textrm{LeetCode169—majority-element}$，虽然该题保证了数组中一定存在主元素，但核心思想和$408$的考题是完全一样的。
解法
为了对比，我们首先假设数组是有序的，这样的话我们需要维护一个计数器$\textrm{count=1}$，然后从下标为$1$的元素开始遍历并维护$\textrm{count}$:
- $\textrm{if (a[i] == a[i-1]) count}$++;
- $\textrm{else count = 1;}$
这样的算法不仅可以寻找主元素，同样可以寻找众数。反过来思考，我们用一个可以解决普遍众数的算法来解决主元素问题，那么很可能忽视了主元素特有的性质，使算法变得冗余。
主元素最显著的特征是：个数大于其他元素出现之和，考虑将主元素赋值为$1$，非主元素赋值为$-1$，于是必然有$\textrm{sum(A)>0}$。假设我们找到了正确的主元素$val$，然后进行如下遍历：
- $\textrm{if (a[i] == val) count}$++;
- $\textrm{else count- -;}$
那么$\textrm{val}$在结束时是大于$0$的，而如果我们选取了非主元素$\textrm{A[0]}$为$\textrm{val}$，那么必然在某个下标$\textrm{i=Index}$的时候会有$\textrm{count<0}$。此时我们需要更换$\textrm{val}$的值为$\textrm{A[1]}$然后重新遍历，但实际上我们可以直接$\textrm{A[Index]}$开始遍历而不必回溯到初始$\textrm{val}$的下标。
首先给出实现代码，然后对其原理和正确性做出说明：
cpp code
class Solution
{
public:
int majorityElement(vector<int>& A)
{
int val = -1; //候选值
int count = 0; //计数器
for (int i = 0;i < A.size();i++)
{
if (A[i] == val) count++;
else
{
count--;
//无论何时,能够使count<0的元素一定不是主元素
if(count < 0)
{
//更换为当前值
val = A[i];
count = 1;
}
}
}
return val;
}
};
在遍历的过程中，我们一定可以选取到主元素，但是选到的时候很可能已经被耗去许多个数了，例如在数列$1,0,2,0,3,0,4,0,5,0,0$中，$0$显然为主元素，而最开始的$\textrm{val}$为$1$，随后$0$和$2$使得$\textrm{count<0}$，然后$2$成为新的$\textrm{val}$，一直到最后一个$0$时，已经有$5$个$0$被用去，此时还剩下最后一个数使得$\textrm{val=0}$，程序结束。这种正确并不是偶然的，事实上，上述排列是对主元素而言的最坏情况，假设遍历到主元素为$\textrm{val}$时，已过去了$\textrm{n}$个数，那么要想耗去最多的主元素，必然是非主元素和主元素进行一换一，否则非主元素之间相互残杀，之后留下更多的主元素在后面，而就算进行一换一，因为主元素的个数超过一半，因此也一定会保持$\textrm{count>0}$，最终$\textrm{val}$一定会回到主元素身上。
再换句话说，存在主元素的数组，无论如何排列内部的数，一定存在一个连续子数组，使得以队首为$\textrm{val}$遍历过程中$\textrm{count}$始终大于$0$。而非主元素充当$\textrm{val}$时一定会使得$\textrm{count}$减到$0$，尽管可以用其他数取消耗主元素，但因为其过半的性质，即使一换一也不可能全部消去，从而保证了最终的$\textrm{val}$必然时主元素。
在$\textrm{LeetCode}$的官方题解中有一些图文的说明，可以帮助理解该算法。
Author@Kuroko
GitHub@SuperKuroko
LeetCode@kuroko177
Last Modified: 2021-03-31 19:21
