剑指 输出众数

通过hashmap来做

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        dict={}

        for i in numbers:
            if i not in dict:
                dict[i]=1
            else:
                dict[i]+=1
        for item in dict.keys():
            if dict[item]>len(numbers)//2:
                return item
        return 0

通过分治法，求一个数组中的众数，数量多于一半的数字，即可以通过他的一半数组，一半一半的数组来求解，再归并，判断左面的数字出现次数多还是右边的数字出现次数多。
如果数字可能出现次数不超过一半，那么需要判断一下求出的数字是否次数多于一半，否则返回0.
每次将数组分成一半，直到只剩一个元素，然后如果两边的元素相等，直接返回当前数字为当前片段的众数，如果不相等，则需要判断一下出现的次数哪边的数字多。

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        def find_num(start,end):
            if start==end:
                return numbers[start]

            mid=(end-start)//2+start
            left=find_num(start,mid)
            right=find_num(mid+1,end)

            if left==right:
                return left
            else:
               left_count=sum(1 for item in numbers[start:end+1] if item==left)
               right_count=sum(1 for item in numbers[start:end+1] if item==right)

               if right_count>left_count :
                   return right
               else:
                    return left
        if len(numbers)==0:
            return 0
        result=0
        result=find_num(0,len(numbers)-1)
        if sum(1 for item in numbers if item==result)>len(numbers)//2:
            return result
        else:
            return 0

摩尔投票法，当下一个元素与前一个相同，标志值加等于1,如果不相同则减一，如果一定存在大于半数的元素，当循环结束标志值大于0，则说明当前值为答案，如果不一定存在大于半数的值，则需要对当前值进行一次判断。

大于n分之一，使用n-1个候选值 大于1/3 使用2个 大于1/2 使用1个

class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        cnt=0
        for item in numbers:
            if cnt==0:
                tmp=item
                cnt+=1
            else:
                if item==tmp:cnt+=1
                else:cnt-=1
        if sum(1 for item in numbers if item==tmp)>len(numbers)//2 and cnt>0:
            return tmp
        return 0

但是俺在这里发现了一个优化，如果最后得到的可抵消票数是 0 的话，那他已经无缘票数能超过一半的那个人了。因为本来可能有希望的，但是被后面的一张不同的票抵消掉了。所以，在这里可以直接返回结果，无需后面的计算了。
如果最后得到的抵消票数不为 0 的话，那说明他可能希望的，这是我们需要一个阶段来验证这个候选人的票数是否超过一半—— 计数阶段。
所以摩尔投票法分为两个阶段：抵消阶段和计数阶段。
抵消阶段：两个不同投票进行对坑，并且同时抵消掉各一张票，如果两个投票相同，则累加可抵消的次数；
计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定。
摩尔投票法经历两个阶段最多消耗 O(2n)O(2n) 的时间，也属于 O(n)O(n) 的线性时间复杂度，另外空间复杂度也达到常量级。
理解摩尔投票法之后，我们再回到题目描述，题目可以看作是：在任意多的候选人中，选出票数超过⌊ 1/3 ⌋的候选人。

作者：wotxdx
链接：https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。