摩尔投票算法

什么是摩尔投票算法

摩尔投票法（Boyer-Moore Majority Vote Algorithm）是一种时间复杂度 为O(n),空间复杂度为O(1)的方法，它多数被用来寻找众数，它由 Robert S. Boyer 和 J Strother Moore 在1981年提出

算法思想

摩尔投票法的思想很简单，就是把寻找众数的过程当作一次选举大会，我们先选出一个候选元素 goal，然后他的票数为count，通过遍历数组，当前数组中的元素和候选元素相同时，count++，不同时，count–，当count==0时，则更换新的候选人。

摩尔投票算法的步骤 总结一下：
1.如果票数为0，将当前元素设为候选元素，并将票数设置为1。
2.如果当前元素等于候选元素，则票数加1。
3.如果当前元素不等于候选元素，则票数减1。

相关例题

169. 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        int n=nums.length;
        int count = 0;
        int goal = 0;//候选人
        for(int i =0;i<nums.length;i++){
            if(count ==0){
                goal =  nums[i];
                count =1;
            }else if(nums[i] == goal){
                count++;
            }else{
                count--;
            }
        }
        return goal;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

摩尔投票法的扩展题目

229. 多数元素 II

解题思路

这道题和上面题有所不同，这个题可能会出现一到两个元素，也就是一到两个候选人的出现，而每个候选人的票数大于 总人数的三分之一即可
需要注意的是 我们除了想到当前元素与候选人1和候选人2是否相等时，还要想到不是他俩时，会怎么办

代码奉上

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();//返回的元素集合
        if(nums == null|| nums.length ==0){
            return res;
        }
        int goal1=0;//候选人1
        int goal2=0;//候选人2
        int count1 =0;//1的票数
        int count2 =0;//2的票数
        for(int num:nums){//开始遍历
            if(num ==goal1){//当数组和1相等时，1的票数+1，继续遍历
                count1++;
                continue;
            }
            if(num ==goal2){//当数组和2相等时，2的票数+1，继续遍历
                count2++;
                continue;
            }
            //当前值既不是1也不是2时，先判断两者的票数是否为0；如果为0，则更新候选人
            if(count1 ==0){
                goal1 =num;
                count1++;
                continue;
            }
            if(count2 ==0){
                goal2 =num;
                count2++;
                continue;
            }
            //若两者的票数都不为0，且当前数组都不是1，2时，两者票数--
            count1--;
            count2--;
        }
        //上一轮遍历是为了找出候选人，还要判断是否大于n/3，则需要重新遍历
        count1=0;
        count2=0;
        for(int num:nums){
            if(num ==goal1){
                count1++;
            }else if(num ==goal2){
                count2++;
            }
        }
        if(count1>nums.length/3){//当票数大于 n/3时，加入集合
            res.add(goal1);
        }
        if(count2>nums.length/3){
            res.add(goal2);
        }
        return res;
    }
}
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
42
43
44
45
46
47
48
49
50
51
52
53