多数元素
Majority Element
本机进度仅保存在当前浏览器
题目描述
给定一个大小为 n 的数组，其中多数元素指出现次数大于 n/2 的元素。你可以假设数组非空且多数元素一定存在，请找出它。进阶：尝试空间复杂度 O(1)、时间复杂度 O(n) 的解法。
示例：nums = [2, 2, 1, 1, 1, 2, 2]，输出 2。
解题思路
- 哈希计数是平凡解法，但要 O(n) 空间；题目保证多数元素过半，可用 Boyer-Moore 投票法做到 O(1) 空间。
- 维护候选数 candidate 与票数 count：遇到相同元素票数加一，不同则减一，减到零就换当前元素当候选。
- 正确性直观理解：多数元素与其他所有元素"捉对抵消"后仍有剩余，因此最终候选一定是它。
参考实现
查看参考实现Python · 建议先自行作答
def majorityElement(nums):
# Boyer-Moore 投票：不同元素互相抵消，多数元素必有剩余
candidate, count = 0, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate