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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        # 这个空间复杂度高,counter简单易理解
        '''
        from collections import Counter
        c = Counter(numbers)
        for k,v in c.items():
            if v > len(numbers) / 2:
                return k
        '''
        # 这个是针对于众数的消解法，题目表明有解，所以直接返回最后剩下的即可 
        candidate = numbers[0] # 初始候选
        count = 1 # 候选者计数
        n = len(numbers)
        for i in range(1, n):
            if numbers[i] != candidate: # 不等于候选者
                count -= 1 # 消解一个
                if count == 0: # 如果把当前候选者消解没了
                    candidate = numbers[i] # 设置当前值为候选者 
                    count = 1 # 新候选者计数
            else:
                count += 1 # 等于候选者计数加一
        return candidate