摩尔投票法

力扣229

Posted by songjiu on July 30, 2019

该方法应用于求序列中,超过总数个数1/2、1/3…1/n的众数的情况,且该方法空间复杂度为常数,可以避免使用dict和map。

原理

超过总数个数的1/n的数字肯定小于等于n-1个,比如选择一个序列当中,超过序列总数一半(1/2)的数字,那这样的数字至多有一个(n=2,2-1=1),不可能有俩都大于总数个数二分之一的数,n等于其他时同理。
摩尔投票法,遍历整个序列,首先选中n-1个数字进入候选池,每个候选池当中的数字拥有一个计数器,初始为1。继续遍历整个序列,当出现这n-1个数字当中的数字时,该数字的计数器+1,出现这n-1个数字以外的数字时,这n-1个数字的全部计数器-1,当某个数字的计数器减少到0时时,补充新进的数字进入候选池。

问题

当整个序列当中不存在满足要求的数字时,摩尔投票法可能会出错,比如序列“1114567”,不存在长度超过总长一半(1/2)的众数,但是使用摩尔投票法,在遍历到‘6’的时候,会将之前的众数1清空,从而当遍历到数字‘7’的时候,数字‘7’进入候选池,然而数字‘7’明显不满足要求。因此在整个摩尔投票法的最后,还需要验证产生的候选数字是否满足大于总长的1/n这一条件。

题目概述

题目概述

代码

            res=[]
        a,b=0,0
        num1,num2=None,None
        for i in nums:
            if i==num1:
                a+=1
            elif i==num2:
                b+=1
            else:
                if num1==None or num2==None:
                    if num1==None:
                        num1=i
                        a=1
                    else:
                        num2=i
                        b=1
                else:
                    a-=1
                    b-=1
                    if a==0:
                        num1=None
                    if b==0:
                        num2=None
        length=len(nums)
        if nums.count(num1)>length//3:
            res.append(num1)
        if num1!=num2:
            if nums.count(num2)>length//3:
                res.append(num2)
        return res