波义尔摩尔投票算法（Boyer-Moore Voting Algorithm）

Posted on   |   Updated on | In | | Visitors

简介

The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981,[1] and is a prototypical example of a streaming algorithm.

波义尔摩尔投票算法是一种使用线性时间复杂度和常数空间复杂度来找到数组的主要元素（出现超过一半次数的元素）。

题目: 169. Majority Element。找出数组中出现超过一半的元素。

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

《剑指Offer》中的解释

遍历数组的时候保存两个值：一个是数组中的数字，另一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，那么需要保存下一个数字，并把次数设为1.由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时的对应数字。

整个过程想象成一次投票选举

投票规则：大屏幕上只允许出现一位候选人。如果选举人投的票不是当前候选人，那么让当前候选人票-1，如果是，则+1。

OK，我们现在把所有数组的元素当成是选举人举出的号牌。我们先考虑最极端的情况：最后的winner以一票之差险胜。也就是元素出现的次数为n//2+1。这种情况是如何出现的呢，假设数组是这样的：

1
[7, 7, 7, 7, 1, 2, 3]

没有投7的选举人假设在一开始知道了最有潜力的winner即7号，那么他们‘同仇敌忾’，将-1的票都投在了7号上，这种情况7号一直处于大屏幕中，没有更换过候选人。但是最后也没能打败7号，因为7号最后还保留一票。

另外一种非极端的情况，没有投7的选举人产生了‘内讧’：

1
[7, 1, | 2, 3, | 7, 7, 7]

首先7号得到一票，然后被1号干掉，接着2号称为候选人，被3号干掉。3号的票浪费在了‘自己人’身上，即‘我们中出了一个叛徒’。就算团结起来都干不过7号，所以winner还是7号。

最后附上LeetCode上的Python代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

参考：