1.什么是摩尔投票法
在⼀个⽆序数组中，存在⼀个数，它出现的次数⼤于数组长
度的⼀半。输出这个数
⼀、排序、遍历
⼆、摩尔投票法
摩尔投票算法是⼀种使⽤线性时间和常数空间查找⼤部分元素序列的算法。
最简单的形式就是，查找输⼊中重复出现超过⼀半以上(必须⼤于n/2，等于不算)的元素。如果序列中没有这种元素，算法不能检测到正确结
果，将输出其中的⼀个元素之⼀。
如果不能保证输⼊数据中有占有⼀半以上的元素，需要再遍历⼀下验证。
满⾜两个先决条件
1、出现超过⼀半以上(n/2)的元素有且只有⼀个；
2、这个元素⼀定存在
算法步骤
我们维护⼀个局部变量作为当前查找元素，⼀个局部变量作为计数器，
当遍历开始的时候，此时计数（count）为0，则将数组第⼀个元素作为当前查找元素；
当遍历的元素与查找元素相等，计数加1；反之则-1；
若当计数为0时，将下⼀个元素作为当前查找元素，继续重复以上操作；当遍历结束时，当前查找元素则为⽬标元素
摩尔投票法分为两个核心步骤
投票阶段：投票人之间票数进行抵消
计数阶段：计算对抗结果最后剩下的那个候选人的票数是否有效
2.例题
题目来自LeetCode
169 多数元素
题目要求 ：
169. 多数元素 - 力扣（LeetCode） (leetcode-cn.com)
解题思路：
1.我们先定义一个候选人 就是数组的第一个元素
2.然后定义一个记录候选人次数的count 初始化count
3.然后for循环遍历 如果有候选人那么我们的count就++，反之则- -
4.如果count为0时，就更换候选人
源码附上：
class Solution { public int majorityElement(int[] nums) { int len=nums.length; int major=nums[0];//遍历第一个元素，候选人是2 int count=0; for(int i=0;i<len;i++){ //如果数组中还有2的话我们的count就++； if(nums[i]==major){ count++; }else{ //如果没有就减1 count--; } //如果count=0的时候就更换候选人 if(count==0){ //更换候选人 major=nums[i];//重新赋值major //票数重置为1 count=1; } } return major; } }
这种情况只能对于多数存在的情况下 比如[4,5,6]major等于6显然是错误的
所以对于不一定存在多数的情况下 我们需要在求出major的情况下 在遍历一遍
统计count的次数是否大于数组长度的一半
1710.主要元素
题目描述：
源码附上：
class Solution { public int majorityElement(int[] nums) { int len=nums.length; int major=nums[0];//遍历第一个元素，候选人是2 int count=0; for(int i=0;i<len;i++){ if(count==0){ //更换候选人 major=nums[i];//重新赋值major //票数重置为1 } //如果数组中还有2的话我们的count就++； if(major==nums[i]){ count++; }else{ //如果没有就减1 count--; } //如果count=0的时候就更换候选人 } count=0; for(int num:nums){ //遍历一遍 记录count的次数 if(num==major){ count++; } } return(count<=len/2)?-1:major; //根据条件判断如果长度超过数组长度的一半 就输出major 反之则输出-1 } }
以上就是小王同学给大家带来的两道经典的摩尔投票法的例题
