数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入:
[1, 2, 3, 2, 2, 2, 5, 4, 2]
输出:2
限制：1 <= 数组长度 <= 50000
来源：剑指Offer 面试题39
相关企业：
| 公司 | 出现时间 |
|---|---|
| 字节跳动 | 2020.06 |
解法：摩尔投票
时间复杂度：O(n)
空间复杂度：O(1)
思路：
- 票数和： 由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1 ，非众数的票数为 −1 ，则一定有所有数字的票数和 >0 。
- 票数正负抵消： 设数组 nums 中的众数为 x ，数组长度为 n 。若nums的前a个数字的票数和 =0 ，则数组后(n−a)个数字的票数和一定仍>0 （即后 (n−a) 个数字的 众数仍为 x ）。
代码：
def majorityElement(self, nums: List[int]) -> int:
votes = 0
for x in nums:
if votes == 0: num = x
votes += 1 if x == num else -1
return num
