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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return int整型
#
class Solution:
    def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:
        # write code here
        # 用字典做哈希表，记录元素出现次数，但是空间复杂度是O(n)，并不符合要求
        # 只有一个元素直接返回
        # if len(numbers) == 1:
        #     return numbers[0]

        # hash = {}
        # for n in numbers:
        #     if n not in hash:
        #         hash[n] = 1
        #     else:
        #         hash[n] += 1
            
        #     if hash[n] > len(numbers) // 2:
        #         return n

        # return 0
        # 候选法
        # 设定一个候选元素，计数器为0
        candidate = -1
        count = 0

        for n in numbers:
            # 说明当前没有候选元素，将当前元素设置为候选元素
            if count == 0:
                candidate = n
                count += 1
            # 否则将候选元素与当前元素进行比较，如果相同则计数器+1，不相同减1
            else:
                if candidate == n:
                    count += 1
                else:
                    count -= 1
        # 题目保证了数据有正解，那可以直接返回
        return candidate
        # 保险起见可以再遍历一下确认它出现次数是不是真的超过了一半
        count = 0
        for n in numbers:
            if n == candidate:
                n += 1
                if n > len(numbers) // 2:
                    return candidate
        return 0