博耶·摩尔多数投票算法

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

LeetCode #169. Majority Element

LeetCode #229. Majority Element II

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

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. 遇到相同的数就更新计数
  2. 遇到不同的数就把计数减 1
  3. 之前的计数已经是 0 了,那就把当前遍历的数作为假定的众数

隐含的信息是:

  1. 如果 a 是结果的众数,那么在原数组中删掉 a 和任意其它一个数,在结果数组中 a 仍然是众数。 所以在计数归零后,我们可以任选一个数,在当前更小的数组中得到的众数,仍然是原数组的众数。
  2. 这种一次遍历是有前提的,如果题目没有假定一定存在众数,那么最后得到的值不一定是众数。比如对于输入数组 [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 的数组作为当前众数,其实也就一样处理了。