摩尔投票法学习笔记

博耶-摩尔多数投票算法（英语：Boyer–Moore majority vote algorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和 J·斯特罗瑟·摩尔在 1981 年发表，也是处理数据流的一种典型算法。

简介

首先我们给出背景：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

这个问题简单来说就是求众数的问题，一个简单的解决办法是使用哈希表记录元素出现的次数，然后遍历哈希表寻找满足条件的元素，时间复杂度为 O(n)、空间复杂度为 O(n)。然而我们希望找到一种时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，也就是下面要讲的摩尔投票法。

算法思想

摩尔投票法的基本思想：在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

具体来说，我们设置一个计数器，在遍历时遇到不同数字时就将计数器 -1，遇到相同数字时就 +1，只要在计数器归 0 时就重新假定当前数字为众数再继续遍历，那么到了最后，计数器记录的那个数字「可能」就是众数。最后再次遍历一遍数组，确定其是否为众数。

例题

LeetCode 169. 多数元素

{% note info %}

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

{% endnote %}

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

{% note info %}

解题思路：基本的摩尔投票法

设置一个计数器，在遍历时遇到不同数字时就将计数器 -1，遇到相同数字时就 +1，只要在计数器归 0 时就重新假定当前数字为众数再继续遍历，那么到了最后，计数器记录的那个数字可能就是众数。最后再次遍历一遍数组，确定其是否为众数。

{% endnote %}

参考代码：

class Solution:
    # 摩尔投票
    def majorityElement(self, nums: List[int]) -> int:
        major, cnt = 0, 0
        for num in nums:
            if cnt == 0:
                major = num
            if major == num:
                cnt += 1
            else:
                cnt -= 1
        cnt = 0
        for num in nums:
            if major == num:
                cnt += 1
        return major if cnt > len(nums) // 2 else 0

LeetCode 229. 求众数 II

{% note info %}

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

{% endnote %}

示例 1：

输入：[3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

{% note info %}

解题思路：对摩尔投票法拓展到 ⌊ n/k ⌋

与上一题不同的是，我们需要统计出现次数超过 n / 3 的数。

我们可以不失一般性的将其拓展为「统计出现次数超过 n / k 的数」

可以证明，出现次数超过 n / k 的数最多只有 k - 1 个。否则必然违背「数总共只有 n 个」或者「当前统计的是出现次数超过 n / k 的数」的前提条件。

我们可以用 k - 1 个变量来代表这 k - 1 个候选数及其出现次数。

类似的，设置 k - 1 个计数器，在遍历时遇到不同数字时就将计数器 -1，遇到相同数字时就 +1，只要在计数器归 0 时就重新假定当前数字为众数再继续遍历，那么到了最后，计数器记录的那个数字可能就是众数。最后再次遍历一遍数组，确定其是否为众数。

{% endnote %}

参考代码：

class Solution:
    # 摩尔投票法
    def majorityElement(self, nums: List[int]) -> List[int]:
        # 出现次数超过 n / k 的数最多只有 k - 1 个
        a, b = 0, 0
        c1, c2 = 0, 0
        for num in nums:
            if c1 != 0 and num == a:
                c1 += 1
            elif c2 != 0 and num == b:
                c2 += 1
            elif c1 == 0:
                a, c1 = num, c1 + 1
            elif c2 == 0:
                b, c2 = num, c2 + 1
            else:
                c1, c2 = c1 - 1, c2 - 1
        # 再进行一次遍历，检查
        c1, c2 = 0, 0
        for num in nums:
            if num == a:
                c1 += 1
            elif num == b:
                c2 += 1
        ans = []
        if c1 > len(nums) // 3:
            ans.append(a)
        if c2 > len(nums) // 3:
            ans.append(b)
        return ans

参考资料

• 多数投票算法
• 【宫水三叶の相信科学系列】详解摩尔投票为何能推广到 n / k 的情况