摩尔算法是很久之前看到的一种算法，主要用于求解众数，求解众数不是很难，但是使用常数级空间确实比较难的，可以说是一种很巧妙的算法，因此分享给大家。
定义摩尔投票算法（Boyer–Mooremajorityvotealgorithm），以下是摩尔投票算法在维基百科上的定义。
摩尔投票算法（Boyer–Mooremajorityvotealgorithm）Boyer–Mooremajorityvotealgorithm中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在年发表，也是处理数据流的一种典型算法。论文地址
根据摩尔投票算法所说，我们可以简单抽象为以下数学模型：已知一组长度为n的数据arrays，求出其中元素占比较多的元素们。（通常占比会是1/2以上，1/3以上等等）。
算法前提这里我们需要理解摩尔投票中何为占多数元素，也就是元素总占比超过一个比例。\
如果是选出占比最多的一个元素，那么占比需要是大于1/2。如果是选出占比最多的两个元素，那么各个元素占比均需要大于1/3。如果是选出占比最多的m个元素，那么各个元素占比需要是大于1/(m+1)。
算法思路第一步，初始化候选人们candidates以及候选人的票数。第二步，扫描arrays：扫描过程中候选人的替换以及票数增减规则如下
如果与某个候选人匹配，该候选人票数加1，继续扫描arrays，重新开始匹配。如果与所有候选人都不匹配，检查候选人票数，如果为0，替换该候选人，不再往下检查。如果与所有候选人都不匹配，检查候选人票数，如果不为0，继续检查一个候选人。第三步，扫描结束以后，检查所有候选人的票数是否大于1/（candidates.length+1）加以验证。如果大于，则候选人成立，不大于则候选人剔除掉。从算法思路上来看，其实摩尔投票算法的核心思想就是相互抵消。下面就是摩尔投票算法的典型代表题目。
摩尔投票算法例题求众数I求众数I是初级摩尔投票问题，求元素占比大于1/2的元素。
问题描述力扣给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于?n/2?的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
问题分析只有一个候选者，是最好解决的，只需要考虑所扫描到的元素是不是候选元素，是票数加，不是则减，同时注意票数归零时候的候选元素替换。
代码classSolution{publicintmajorityElement(int[]nums){//摩尔投票intcount=0;intcandidate=nums[0];for(intnum:nums){if(count==0)candidate=num;if(candidate==num)count++;elsecount--;}returncandidate;//排序//Arrays.sort(nums);//returnnums[nums.length/2];//哈希表计数//HashMapInteger,Integerdict=newHashMap();//intlen=nums.length;//if(len==1
len==2)returnnums[0];//intres=0;//for(intnum:nums){//if(dict.containsKey(num)){//intcount=dict.get(num);//if(count=len/2){//res=num;//break;//}//dict.put(num,count+1);//}else{//dict.put(num,1);////System.out.println(dict.containsKey(num));//}//}//returnres;}}
时间复杂度：O(N)空间复杂度：O(1)
求众数II求众数II是进阶版本的运用摩尔投票，求元素占比超过1/3的元素。
问题描述力扣给定一个大小为n的整数数组，找出其中所有出现超过?n/3?次的元素。进阶：尝试设计时间复杂度为O(n)、空间复杂度为O(1)的算法解决此问题。
问题分析这个问题如果看了摩尔投票的算法思路，其实就很简单了，只不过第一题的候选人数增加一个，票数相应变为两个候选者的，同时注意抵消票数时，二者不互相抵消即可。
代码classSolution{publicListIntegermajorityElement(int[]nums){int[]tmpCandidates=newint[]{nums[0],nums[0]};int[]votes=newint[2];ListIntegercandidates=newArrayList();for(intnum:nums){//匹配候选人if(tmpCandidates[0]==num){votes[0]++;continue;}if(tmpCandidates[1]==num){votes[1]++;continue;}//检查票数if(votes[0]==0){tmpCandidates[0]=num;votes[0]++;continue;}if(votes[1]==0){tmpCandidates[1]=num;votes[1]++;continue;}//均不匹配，且不替换候选人votes[0]--;votes[1]--;}//扫描结束，检查候选人是否合格Arrays.fill(votes,0);for(intnum:nums){if(tmpCandidates[0]==num)votes[0]++;elseif(tmpCandidates[1]==num)votes[1]++;}if(votes[0]nums.length/3)candidates.add(tmpCandidates[0]);if(votes[1]nums.length/3)candidates.add(tmpCandidates[1]);returncandidates;}}
时间复杂度：O(N)空间复杂度：O(1)
总结摩尔投票算法初步讲解就到这里结束了，这一算法其实思路并不难，总结成上述算法思路进行求解还是比较清晰的。除此之外，一定要搞清楚摩尔投票算法的使用前提。同时，有兴趣，大家可以思索下这一算法在这一前提下的可行性，为什么算法可以成立。
IT涓涓清泉