import collections
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Boyer-Moore 算法
        # 記數
        count = 0
        # 候選人
        can = None
        # 遍歷 List
        for num in nums:
            # 假如記數為 0，則記錄候選人
            if count == 0: can = num
            # 假如是候選人，則加1，不是候選人則減1
            if num == can:
                count += 1
            else:
                count -= 1
        return can