Boyer-Moore Majority Vote Algorithm

Posted on In

起源

Boyer-Moore Vote Algorithm由UT Austion的Robert S. Boyer 和 J Strother Moore提出，是为了解决找出一个数组中出现次数大于n / 2 的数的，其中n为数组长度，乃至可以类推到找出k - 1个出现次数大于n / k的数。这个问题直观上来可以使用哈希表统计出现次数，不过对于算法优化的追求，使得许多存储空间是不必要的，通过使用Boyer-Moore Majority Vote Algorithm（可译为摩尔投票）空间复杂度可以降低到O(1)，这道题现在经常出现在公司面试题中。

intution

如果存在出现次数大于n / k的 k - 1个数，那么剩下的数字的总数必然小于(k - 1) * k / n，比如找出大于一半的数，如果这个数存在则剩下所有的数的出现次数总和必然小于一半。即将数组抽象为两个部分，出现n / 2次数的数k，和非k。

算法

  • Initialize an element m and a counter i with i = 0
  • For each element x of the input sequence:
    • If i = 0, then assign m = x and i = 1
    • else if m = x, then assign i = i + 1
  • else assign i = i − 1
  • Return m
    用找大于n / 2来举例，设置一个candidate和count，如果找到一个数等于candidiate则count + 1，否则count - 1如果count变成0，则将candidate更新为当前指针所指的新数字。
    下图来自于wikipedia，直观上说明了为什么这个算法是可行的：


例子

Leetcode 169 Majority Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for(int num : nums){
        if(candidate == num)
            ++count;
        else if(count == 0){
            count = 1;
            candidate = num;
        }
        else
            --count;
    }
    return candidate;
}

这是这个算法的典型应用，找出出现次数大于一半的数字，这个数字保证存在

Leetcode 229 Majority Element II

这个是拓展，找出出现次数大于n / 3的两个数字，这两个数字不一定存在，我们只需要在最后遍历下数组，看看剩下的两个candidate能否满足条件即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public List<Integer> majorityElement(int[] nums) {
    int count1 = 0;
    int count2 = 0;
    int candidate1 = 0;
    //注意candidate1 和 candidate2初始化应该不同
    int candidate2 = 1;
    for(int num : nums){
        if(num == candidate1)
            count1++;
        else if(num == candidate2)
            count2++;
        else if(count1 == 0){
            count1 = 1;
            candidate1 = num;
        }
        else if(count2 == 0){
            count2 = 1;
            candidate2 = num;
        }
        else{
            --count2;
            --count1;
        }
    }
    List<Integer> res = new LinkedList<>();
    count1 = 0;
    count2 = 0;
    for(int num : nums){
        if(num == candidate1){
            ++count1;
        }
        else if(num == candidate2){
            ++count2;
        }
    }
    if(count1 > nums.length / 3)
        res.add(candidate1);
    if(count2 > nums.length / 3)
        res.add(candidate2);
    return res;
}

当然这道题的思想还有别的拓展，如之前我有写过的Leetcode525，也是类似的，遇见+1，没有遇见-1，核心依然在于将整个数组抽象为两个部分。