难度: Medium
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3] 输出：[3]
示例 2：
输入：nums = [1] 输出：[1]
示例 3：
输入：nums = [1,2] 输出：[1,2]
提示：
1 <= nums.length <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
Submission
运行时间: 26 ms
内存: 17.4 MB
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
# 摩根投票 每三个不一样的数抵消一次
numA = numB = None
cntA = cntB = 0
for num in nums:
if num == numA:
cntA += 1
elif num == numB:
cntB += 1
elif numA is None:
numA = num
cntA += 1
elif numB is None:
numB = num
cntB += 1
else:
cntA -= 1
cntB -= 1
if not cntA:
numA = None
if not cntB:
numB = None
# 个数验证
cntA = cntB = 0
for num in nums:
if num == numA:
cntA += 1
elif num == numB:
cntB += 1
s = len(nums)//3
ans = []
if cntA > s:
ans.append(numA)
if cntB > s:
ans.append(numB)
return ans
Explain
题解采用了摩尔投票算法的扩展版本，用于解决找出所有出现超过 ⌊ n/3 ⌋ 次的元素的问题。算法核心思想是维护两个候选元素以及它们的计数。遍历数组时，若当前元素等于其中一个候选元素，则增加该候选的计数；若不等于任何候选且有候选位置为空，则将当前元素设为新候选并计数为1；若两个候选都非空且当前元素与它们都不相等，则同时减少两个候选的计数。每次减计数时，若某候选的计数减到0，则释放该候选。最后，再次遍历数组以验证两个候选的真实计数是否超过 ⌊ n/3 ⌋，符合条件的则加入结果列表。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
# 初始化两个候选及其计数器
numA = numB = None
cntA = cntB = 0
# 第一次遍历：选出两个候选元素
for num in nums:
if num == numA:
cntA += 1
elif num == numB:
cntB += 1
elif numA is None:
numA = num
cntA += 1
elif numB is None:
numB = num
cntB += 1
else:
cntA -= 1
cntB -= 1
if not cntA:
numA = None
if not cntB:
numB = None
# 第二次遍历：验证候选元素的计数是否满足条件
cntA = cntB = 0
for num in nums:
if num == numA:
cntA += 1
elif num == numB:
cntB += 1
s = len(nums)//3
ans = []
if cntA > s:
ans.append(numA)
if cntB > s:
ans.append(numB)
return ans
Explore
在摩尔投票扩展算法中，我们维护两个候选元素来确保找到所有出现次数超过 ⌊n/3⌋ 的元素，因为数学上不可能有超过两个元素的出现次数都超过 ⌊n/3⌋。算法通过不断调整这两个候选以确保至少包含了那些频率高的元素。如果有任何元素的出现次数确实超过了 ⌊n/3⌋，那么经过第一次遍历后，这些元素中至少有一个会成为候选元素。
如果没有元素的出现次数超过⌊n/3⌋，算法的第二次遍历将会验证这一点。在第一次遍历中，算法可能会选择两个候选元素，但在第二次遍历时对这些候选进行计数验证时，将发现他们的计数未能超过 ⌊n/3⌋。因此，这些候选将不会被添加到最终的结果列表中，从而正确反映出没有元素满足条件。
算法通过持续调整候选元素来响应输入数组的元素分布。如果一个元素频繁出现，它将有更大的机会成为候选之一或通过减少其他候选的计数来保持候选地位。第一次遍历确保将出现频率高的元素保留为候选，但这并不保证这些候选的真实计数确实超过 ⌊n/3⌋，这需要通过第二次遍历的验证来确定。第二次遍历是必要的，因为第一次遍历只是基于相对比较和候选调整，而没有进行实际计数。