Python解法

# -*- coding:utf-8 -*-
class Solution:#不用count()  时间复杂度为O(n)
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        n=len(numbers)
        num=numbers[0]
        cnt=1
        #如果存在一个数大于一半数组长度的话
        for i in range(n):
            if num==numbers[i]:
                cnt+=1
            else:cnt-=1
            if cnt==0:#重新换一个数试试
                num=numbers[i]
                cnt=1
        #验证阶段 如果num个数大于一半数组长度则 num是确定的且 cnt*2>n
        cnt=0
        for i in range(n):
            if num==numbers[i]:
                cnt+=1
        return num if cnt*2>n else 0