博耶·摩尔多数投票算法

Posted on November 18, 2020 in Algorithm, LeetCode

O(n) 时间、O(1) 空间，查找输入数据的众数。

为了找出输入数据中的众数，最直观的解法就是计数了：

1# most_common(1) = [('b', 2)]
2Counter(["a", "b", "b"]).most_common(1)[0][0]		# 'b'

把每一个值当作 key，空间占用是 O(n)，而多数投票算法可以做到只使用 O(1) 的空间，思想是这样的：

在一组数据中，「众数」代表了什么？表示这个数出现次数在一半以上。也就是说，众数的数量大于其它所有数的出现次数之和。

我们可以采用抵消的思想，众数和其它数字一一抵消，最后剩下的数，就是众数了。在上面的例子中，["a", "b", "b"] 抵消一次之后变成了 ["b"]。

 1# LeetCode #169，题目假定众数一定存在
 2class Solution:
 3    def majorityElement(self, nums: List[int]) -> int:
 4        curRes, curCount = nums[0], 0
 5        for n in nums:
 6            if n == curRes:
 7                curCount += 1
 8            elif curCount > 0:
 9                curCount -= 1
10            else:
11                curRes, curCount = n, 1
12        return curRes

我们随便取了 nums[0] 作为众数，初始计数为 0。

遇到相同的数就更新计数
遇到不同的数就把计数减 1
之前的计数已经是 0 了，那就把当前遍历的数作为假定的众数

隐含的信息是：

如果 a 是结果的众数，那么在原数组中删掉 a 和任意其它一个数，在结果数组中 a 仍然是众数。所以在计数归零后，我们可以任选一个数，在当前更小的数组中得到的众数，仍然是原数组的众数。
这种一次遍历是有前提的，如果题目没有假定一定存在众数，那么最后得到的值不一定是众数。比如对于输入数组 [1, 2, 3, 4, 5] 最后会返回一个值，但是不会是众数。所以当不确定是否存在众数时，应该再次遍历确认一下 nums.count(curRes) 是否超过 len(nums) / 2。

解决了 N / 2 的众数，我们也可以解决 N / 3 的情况，即 LeetCode #229. Majority Element II。

还是同样的思想：

如果 a、b 出现都超过了 N / 3，那么把其它所有数字归为一组，出现次数肯定小于 N / 3。 a、b 分别和其它数字一一抵消，最后 a、b 仍然会剩下。

但是这里需要注意的是，a 和 b 是不能相互抵消的，所以我们需要分别维护 2 个当前众数和对应的计数：

 1class Solution:
 2    def majorityElement(self, nums: List[int]) -> List[int]:
 3        a, ac = None, 0
 4        b, bc = None, 0
 5        for n in nums:
 6            if n == a:
 7                ac += 1
 8            elif n == b:
 9                bc += 1
10            elif a is None:
11                a, ac = n, 1
12            elif b is None:
13                b, bc = n, 1
14            else:
15                ac -= 1
16                if ac == 0:
17                    a = None
18                bc -= 1
19                if bc == 0:
20                    b = None
21
22        res = []
23        if nums.count(a) > len(nums) / 3:
24            res += [a]
25        if nums.count(b) > len(nums) / 3:
26            res += [b]
27        return res

因为题目并没有假定结果一定存在，所以需要再一次遍历来校验。

解决了 N / 2 和 N / 3，那么出现次数大于 N / K 的问题，可以维护一个长度为 K 的数组作为当前众数，其实也就一样处理了。