难度: Easy
数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1：
输入：[1,2,5,9,5,9,5,5,5] 输出：5
示例 2：
输入：[3,2] 输出：-1
示例 3：
输入：[2,2,1,1,1,2,2] 输出：2
Submission
运行时间: 28 ms
内存: 17.6 MB
class Solution:
def majorityElement(self, nums: List[int]) -> int:
res, cnt = -1, 0
for num in nums:
if not cnt:
res = num
cnt = 1
else:
if res == num:
cnt += 1
else:
cnt -= 1
return res if nums.count(res) > len(nums)//2 else -1
Explain
这个题解采用了摩尔投票算法（Boyer-Moore Voting Algorithm），用于找出数组中的主要元素。算法的基本思路是维护一个候选主要元素和一个计数器。遍历数组时，若计数器为零，则将当前元素设置为候选元素，并将计数器设为1。如果计数器不为零，当遇到与候选元素相同的数时，计数器加1；否则，计数器减1。这样，遍历结束后，候选元素可能是主要元素。然而，由于计数器的减少可能导致非主要元素成为候选，因此需要再次遍历数组来确认候选元素的出现次数是否真的超过了数组长度的一半。若是，则返回该元素；若不是，则返回-1。
时间复杂度: O(N)
空间复杂度: O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> int:
res, cnt = -1, 0 # 初始化候选结果为-1，计数器为0
for num in nums: # 遍历数组
if not cnt: # 如果计数器为0
res = num # 更新候选结果
cnt = 1 # 重置计数器
else: # 如果计数器不为0
if res == num: # 如果当前元素等于候选结果
cnt += 1 # 计数器增加
else: # 如果不等
cnt -= 1 # 计数器减少
# 第二次遍历确认候选元素是否为主要元素
return res if nums.count(res) > len(nums) // 2 else -1 # 如果候选元素出现次数超过一半则返回，否则返回-1
Explore
摩尔投票算法的核心思想是通过对抗消除的方式，找出可能的主要元素。当计数器为正时，表示当前候选元素存在超过其他所有不同元素的数量。遇到一个与候选元素不同的元素时，理论上这两个元素会相互抵消掉一部分影响力，因此需要将计数器减1。这样做的目的是尝试抵消与当前候选元素可能存在的数量对等的其他元素，以帮助确定真正的主要元素。
在摩尔投票算法的第一次遍历后，我们得到了一个可能的候选元素，但这个候选元素可能并非真正的主要元素。因此，在第二次遍历中，我们需要统计这个候选元素在数组中的出现次数，确认它的数量是否确实超过了数组长度的一半。仅当候选元素的出现次数大于数组长度的一半时，我们才可以确定它是主要元素。否则，返回-1表示没有主要元素。
如果数组中的每个元素都是唯一的，那么摩尔投票算法在第一次遍历过程中的候选元素将频繁更换，最终的候选元素将是数组中的最后一个元素。这是因为每次遇到新的元素都会导致当前候选元素的计数器归零，然后将新的元素设置为候选元素。但在第二次遍历的验证中，由于没有任何元素的出现次数超过数组长度的一半，算法最终将返回-1。