LC 169多数元素Majority Element　简单

找出数组中出现次数超过一半的多数元素（题目保证一定存在）。

思路 摩尔投票：不同元素互相抵消，票数归零时更换候选，最终候选即多数元素。时间 O(n)。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = cnt = 0
        for x in nums:
            if cnt == 0:
                ans = x
            cnt += 1 if x == ans else -1
        return ans