摩尔投票算法

什么是摩尔投票算法

摩尔投票法（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;}
}

摩尔投票法的扩展题目

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;//候选人1int goal2=0;//候选人2int 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;}
}