题解 | 数组中出现次数超过一半的数字

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        # 方法一：
        # 排好序的数组，超过一半的长度的元素一定在中间位置出现
        # 将其设为候补，遍历验证其出现次数是否超过长度的一半
        # numbers = sorted(numbers)
        # cond = numbers[len(numbers)//2]
        # count = 0 
        # for i in range(len(numbers)):
        #     if(numbers[i]==cond):
        #         count+=1
        # if count>len(numbers)//2:
        #     return cond

        #法2：
        #通过哈希表，统计每个元素出现的个数
        #将其构建成字典
        # dict_numbers = {}
        # for i in range(len(numbers)):
        #     if numbers[i] in dict_numbers:
        #         dict_numbers[numbers[i]]+=1
        #     else:
        #         dict_numbers[numbers[i]]=1
            
        #     if dict_numbers[numbers[i]]>len(numbers)//2:
        #         return numbers[i]

        #法3:消消乐法，超过一半的元素，一定能与其他元素抵消，并且最后有剩余
        cond=-1#设置候选人为-1
        count=0#候选人出现次数，候选人同+1，不同抵消-1
        for i in range(len(numbers)):
            if count==0:#如果候选人次数为0，重新选人
                cond=numbers[i]#选当前为候选人
                count=1#出现次数重新设为1
            else: #候选人出现次数不等0
                if cond == numbers[i]:#如果与当前候选人相同
                    count+=1 #其出现次数+1
                else:#不同
                    count-=1 #其出现次数-1
        #最后的cond为可能的候选人

        #证明是否真的过半
        count=0
        for i in range(len(numbers)):
            if numbers[i]==cond:
                count+=1
        if count>(len(numbers)//2):
            return cond