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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param numbers int整型一维数组
# @return int整型
#

"""
要解决这个问题，我们可以使用摩尔投票算法（Boyer-Moore Voting Algorithm）。
摩尔投票算法可以在线性时间复杂度O(n)和常数空间复杂度O(1)内找到出现次数超过一半的元素。
摩尔投票算法的基本思想是维护一个候选众数candidate和它的出现次数count。遍历数组，
如果count为0，我们假设当前遍历到的元素是候选众数，并将count设为1。
如果count不为0，我们检查当前元素是否等于candidate，如果等于，count加1，否则count减1。
遍历完数组后，candidate就是我们要找的众数。
"""


class Solution:
    def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
        candidate = None
        count = 0
        for num in numbers:
            if count == 0:
                candidate = num
            if num == candidate:
                count += 1
            else:
                count -= 1
        return candidate