摩尔多数投票算法

一、介绍

博耶-摩尔多数投票算法（英语：Boyer–Moore majority votealgorithm）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表[1]，也是处理数据流的一种典型算法。

这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。对于数据流而言，则不太可能在亚线性空间复杂度的情况下中就寻找到出现频率最高的元素；而对于序列，其元素的重复次数也有可能很低。【来源：维基百科】

二、伪代码

算法可以用伪代码如下表示：

初始化元素m并给计数器i赋初值i = 0
对于输入队列中每一个元素x：
若i = 0, 那么 m = x and i = 1
否则若m = x, 那么 i = i + 1
否则 i = i − 1
返回 m

该算法实现，即便输入序列没有多数元素，这一算法也会返回一个序列元素。然而如果能够进行第二轮遍历，检验返回元素的出现次数，就能判断返回元素是否为多数元素。因此算法需要两次遍历，亚线性空间算法无法通过一次遍历就得出输入中是否存在多数元素。

三、力扣题

原题链接：https://leetcode.cn/problems/find-majority-element-lcci/
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

样例：

其实这题最直观的方法有两种：1）使用哈希表统计每个数字出现的频数，然后查看该元素对应频数是否超过数组长度的一半，以此确认是否为“多数元素”，但这种方法时间复杂度为O(n)，空间复杂度也为O(n)，显然不满足题目要求。2）对数组进行排序，然后查看nums[nums.length/2]元素是否为目标元素即可，此时时间复杂度为排序算法对应时间复杂度，为O(nlogn)，空间复杂度为O(1)，也不满足题目要求。

基于哈希表：

class Solution {// 哈希表public int majorityElement(int[] nums) {// 统计每个数字出现的频数Map<Integer,Integer> freqs=new HashMap<>();for(int num:nums){freqs.put(num,freqs.getOrDefault(num,0)+1);// 判断频数是否超过数组长度的一半if(freqs.get(num)>nums.length/2){return num;}}return -1;}
}

基于排序：

class Solution {// 排序+遍历public int majorityElement(int[] nums) {Arrays.sort(nums);int target=nums[nums.length/2];int counts=0;for(int num:nums){if(target==num){counts++;}}return counts>nums.length/2?target:-1;}
}

投票算法代码（最优解）：

该算法存在的问题：即使数组不存在多数元素，也会返回一个非-1的元素，比如可能仅仅是数组的最后一个元素，所以需要进行二次遍历，统计第一次遍历得到的结果target对应的频数，是否真的是多数元素。时间复杂度为O(2n)->O(n)，空间复杂度为O(1)。

class Solution {// 摩尔投票public int majorityElement(int[] nums) {int target=-1;int counts=0;int i=0;while(i<nums.length){if(counts==0){  // 第一次遇见该数counts=1;target=nums[i];}else {if(nums[i]==target){  // 连续出现该数counts++;}else{  // 出现其他数counts--;}}i++;}// 此时可能target并不是众数，有可能只是数组最后一个元素counts=0;for(int num:nums){if(num==target){counts++;}}return counts>nums.length/2?target:-1;}
}