Boyer–Moore摩尔投票算法

本文介绍在常数空间复杂度下找出数组中多数元素的Boyer–Moore摩尔投票算法

abstract.png

楔子

找出数组中的多数元素:对于一个含N个元素的的无序数组,请找出该数组中出现的多数元素。其中多数元素指的是出现的次数超过一半以上的元素。并假设该数组中一定存在多数元素

对于该问题,最朴素的思路就是遍历数组中的各元素并进行计数,显然该思路下时间、空间复杂度均为线性。而Boyer–Moore摩尔投票算法则可以进一步的将空间复杂度降到常数级别

基本原理

在Boyer–Moore摩尔投票算法中,其维护了两个变量:major多数元素、vote投票数。然后开始遍历数组:

  1. 如果投票数为0时,则将数组中的当前元素作为major多数元素
  2. 如果数组中的当前元素与major多数元素相同,则票数+1;反之减1

遍历结束后,如果该数组中存在多数元素,则major变量返回的一定是多数元素

该算法的理解其实非常简单:在一个多方互相打仗的游戏中,每个己方士兵和对方一个士兵打仗的结局都是一对一同归于尽,则最后还有存活士兵的一方即为胜利方。假设你方士兵数超过总士兵数一半以上,最差的情况下,其他国家的所有士兵都联合起来对付你(即每次都是选择多数元素作为major变量的值);当然其他国家之间也可能会相互攻击(即选择不是多数元素的元素作为major变量的值)。但只要你方士兵内部不要发生内斗、相互对拼消耗,则最后肯定是你方获胜

值得一提的是,之前我们假设了数组中一定存在多数元素,则此时Boyer–Moore摩尔投票算法给出的结果一定是多数元素。但对于一个可能不存在多数元素的数组而言,则需要对该算法给出的结果做进一步检查。具体地,遍历原数组对算法结果进行计数,检查其出现次数是否超过半数以上

实现

这里给出Boyer–Moore摩尔投票算法在Java下的实现,并对数组中可能不存在多数元素的场景进行检验

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
/**
* Boyer–Moore摩尔投票算法
*/
class Solution {
public int majorityElement(int[] nums) {
Integer major = null; // 多数元素
Integer vote = 0; // 投票数

for (Integer num : nums) {
// 票数为0, 直接将当前元素作为多数元素
if(vote == 0) {
major = num;
}
// 当前元素与多数元素相等, 则票数加1
if(num.equals(major)) {
vote++;
} else { // 当前元素与多数元素不等, 则票数减1
vote--;
}
}

// 对摩尔投票算法结果进行检查
int count = 0;
for(Integer num : nums) {
if( num.equals(major) ) {
// 对算法结果进行计数
count++;
}
}
if( count <= nums.length/2 ) {
// 算法结果 不符合多数元素半数以上的要求
major = null;
}
return major;
}
}
0%