剑指Offer39-数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
限制：
1 <= 数组长度 <= 50000
来源：力扣（LeetCode）
链接：力扣
一解
使用摩尔投票法：
-
首先选择一个投票数字
-
遍历数组，如果数字相同，
投票数字 + 1 -
如果数字不相同，
投票数字 - 1，如果数字为 0 ，更换选民
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count, res = 0, nums[0]
for i in nums:
if i == res :
count += 1
else:
count -= 1
if count == 0:
res = i
count = 1
return res
一解
思路与一解相同，优化逻辑：
-
利用
votes += 1 if x == num else -1替换上述对 count 的 + 1 或 -1 操作 -
利用代码执行顺序，省去
count = 1操作
class Solution:
def majorityElement(self, nums: List[int]) -> int:
votes = 0
for num in nums:
if votes == 0: x = num
votes += 1 if x == num else -1
return x