$2013$年$408$统考中的一道数据结构题:若长度为$n$的数组$A$中有某个元素的个数$c$满足$c>(int)n/2$,那么称该元素是主元素。查找一个数组是否有主元素和主元素的值的方法固然有许多:排序后计数,哈希表计数,计数排序等。但在评分标准中写着,要拿到该题的满分,需要实现一个时间复杂度为$O(n)$且空间复杂度为$O(1)$的算法,也就是本文要介绍的$Boyer-Moore$投票算法。

在$LeetCode$中有一道类似的算法题:多数元素,虽然该题保证了数组中一定存在主元素,但核心思想和$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}$的下标。

首先给出实现代码,然后对其原理和正确性做出说明:

$C$++$\ Source \ 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}$的官方题解中有一些图文的说明,可以帮助理解该算法。

$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$

$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$

$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$

$\textrm{Last Modified: 2021-03-31 19:21}$