1、题型归纳

摩尔投票法(Boyer–Moore majority vote algorithm)出自论文，解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为： O ( n ) ，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行 O(n^2) 的时间。当选票有序时，可以很容易编出 O ( n )的程序，首先找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在 O ( n )时间内选出获票最多的，空间开销为 O ( 1 ) 。
最直接的摩尔投票算法是可以直接找到数量超过一半的数。

2、算法步骤

算法主要分为两步：pairing阶段和counting阶段。

第一步：pairing阶段

两个不同选票的人进行对抗，并会同时击倒对方，当剩下的人都是同一阵营，相同选票时，结束。

第二步：counting阶段
计数阶段，对最后剩下的下进行选票计算统计，判断选票是否超过总票数的一半，选票是否有效。

算法演示

这里使用一个常用网站

选票情况为：
A A A C C B B C C C B C C
结果应该是C

3、试题练习

第一题：力扣1710题，求主要元素，试题如下：

 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
 示例 1：
输入：[1,2,5,9,5,9,5,5,5]
输出：5
示例 2：
输入：[3,2]
输出：-1
示例 3：
 输入：[2,2,1,1,1,2,2]
 输出：2
说明：
 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

显然这里有三种方法：使用HashMap进行计数，或者先对数组进行排序，排序之后查找中位数，以及摩尔投票法。

这里我们三种方法都给出：

第一种：摩尔投票法

//摩尔投票法，只能找到超过一半的众数，如果不超过一半，那么在相互抵消的过程中，留下来的可能不是最多的
    //时间复杂度O(n),空间复杂度 O(1)
    public static int majorityElement(int[] nums) {
        //判断是否唯恐
        if(nums.length==0){
            return -1;
        }
        //摩尔投票法
        int num=0;  //记录众数
        int count=0;  //记录次数
        for (int i = 0; i < nums.length; i++) {
            if(count==0){
                num=nums[i];
                count++;
            }else{
                if(num==nums[i]){
                    count++;
                }else{
                    count--;
                }
            }
            System.out.println("当前的众数:"+num+",当前的count:"+count);
        }
        //验证,如果不验证，数组中加入众数不超过一半，经过抵消，可能返回的是最后一个元素
        int check=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==num){
                check++;
                if(check>nums.length/2){
                    return num;
                }
            }
        }
        return -1;
    }

第二种：HashMap键值对

    //hashmap键值对法
    public static int majorityElement3(int[] nums) {
        HashMap<Integer,Integer> hashMap = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            //记录每个元素出现的次数 ，key为对应的元素，值为元素出现的次数
            if(hashMap.containsKey(nums[i])){
                hashMap.put(nums[i],(int)hashMap.get(nums[i])+1);
            }else{
                hashMap.put(nums[i],1);
            }
        }
        //验证结果
        for (Map.Entry<Integer,Integer> entry : hashMap.entrySet()) {
            if(entry.getValue()>nums.length/2){
                return entry.getKey();
            }
        }
       return -1;
    }

第三种：排序取中法

//排序查找法，排序后验证中间的元素是否为大于一半的众数
    //时间复杂度O(nlogn),空间复杂度 O(1)
    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        int res=nums[nums.length/2];
        int count=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==res){
                count++;
                if(count>nums.length/2){
                    return res;
                }
            }
        }
        return -1;
    }

显然这三种方法中，摩尔投票算法的效率是最高的。

第二题：力扣229题，求众数，试题如下：

求众数
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
示例 1：
输入：[3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

很显然本题也可以使用HashMap，这里为了提高效率，我们使用改进的摩尔投票的算法来解决

思路分析：

由于超过三分之一的数最多只可能有两个，所以我们设置这里设置两个待定的超过三分之一的数，然后通过摩尔投票进行抵消，抵消到最后需要检查两个待定的数是否超过三分之一，以及是否为同一个数。

本题目使用摩尔投票法的代码如下：

public static List<Integer> mostPercetnThree(int [] arr){
        List<Integer> list = new LinkedList<>();
        if(arr==null||arr.length==0){
            return list;
        }
        int cond1=arr[0],cond2=arr[0]; //初始化第一候选人和第二候选人均为第一个数
        int count1=0,count2=0; //初始化他们的票都为0
        for (int i = 0; i < arr.length; i++) {
            //如果该票为第一个候选人，则第一个候选人的票数增加，本轮循环结束
            if(cond1==arr[i]){
                count1++;
            //这里如果不结束的化，第下面的第二个if判断也会执行， 因为初始化的时候两个候选人均为arr[0]
                continue;
            }
            //如果该票为第二个候选人，则第二个候选人的票数增加，本轮循环结束
            if(cond2==arr[i]){
                count2++;
                continue;
            }
            //因为初始化的时候，两个候选人都指向arr[0]，这里需要更新候选人
            if(count1==0){
                //如果第一个候选人的票抵消为0,则更新候选人
                cond1=arr[i];
                //为新的候选人+1票
                count1++;
                //结束本轮循环
                continue;
            }
            if(count2==0){
                //更新候选人
                cond2=arr[i];
                //更新第二个候选人的票
                count2++;
                //结束本轮循环
                continue;
            }
  //如果上面条件都没满足，说明当前两个候选人都有票，且当前票不是投给那两个候选人，所以候选人的票需要抵消1
            count1--;
            count2--;
        }
        // 经过上述的投票，此时两个候选人已经出来了，之类需要检查当前候选人票数是否超过三分之一
        count1=0;
        count2=0;
        for (int i = 0; i < arr.length; i++) {
  //这里使用if else就相当于是判断这两个数是否一样了，如果一样的化第二个数的count2显然不会变，始终为0
            if(arr[i]==cond1){
                count1++;
            }else if(arr[i]==cond2){
                count2++;
            }
        }
        if(count1>arr.length/3){
            list.add(cond1);
        }
        if(count2>arr.length&&cond1!=cond2){
            list.add(cond2);
        }
        return list;
    }

推广到选n个超过1/n的也是一样，只需要修改部分代码即可。

4、总结

摩尔投票算法很适合用来求取众数，如果题目设计到求众数，或者主要元素的问题，可以首选摩尔投票算法。