首页 > 代码库 > 算法(7)Majority Element II

算法(7)Majority Element II

题目:找出数组中出现次数大于n/3次的数字

思路:摩尔投票法。所有的帖子中都说:先遍历一遍数组找到备选元素,然后再遍历一遍数组考察下这个元素是否是真的超过n/3,然后就直接上代码,但是现在的问题是:我怎么找到这个备选的元素?!票是怎么投起来的呢?通过参考文章中的代码,大致明白了,醍醐灌顶(http://www.cnblogs.com/grandyang/p/4606822.html)。那么怎么遍历一遍数组然后找到备选元素呢?这个算法还得从找到大于一半的数说起:整个数组中有两个不一样的数的时候,就清除掉这两个一样的数,这样的话,最后一个数组里肯定会剩下一些数的!这就是投票的过程咯,然后遍历下数组,检查下这个被选出来的票就可以了!那么对应于n/3,n/4时,这样的情况会不会存在呢?对应于三个数的情况,数组中最多有2个数满足出现次数大于n/3,那么如果只有一个这样的数呢?比如[7,7,7,5,4,6,8,10]这样的呢?首先777入栈,如果也是单反目前栈里数字不一样的,那么这样两个数字就要出栈了,如此,那么当5,4,6袭来,7肯定就是pass掉了,这是大于n/2情况的分析,那么n/3情况的分析呢?应该是说,准备两个栈,两个栈中分别存着目前的两个候选人,然后每当挑战者来了之后,分别同这两个栈中的数字比较,如果不同,那么两个栈就各出局一个!【这里有个小细节,当两个栈中某个栈是空的,那么就挑战者就占用这个栈了】。所以,同理的话,当找到大于n/4的数字,我们就要准备3个栈了(因为最多也就3个元素),如果哪个栈是空的,挑战者就占着空闲的栈位,否则,如果挑战者不等于栈里的任何一个元素,栈里的元素都得弹出来呢!编程时,注意处理好这个”栈“!

 

答案

算法(7)Majority Element II