1. 题目
2. 分析
说实话,这虽然是一道简单题,但我真没想到LeetCode官方题解会给出这么多种方案。下面就来谈谈如何在O(n)
的时间复杂度下求出本题。
O(n)
复杂度的解法挺难想到。本质上类似于消消乐游戏。如果一个元素是数组中的众数,那么很明显,将众数跟剩余的各个数相消,那么剩下来的那个数就是众数。那么问题来了,如何做到相消?仔细领悟下面这段代码。
3. 代码
class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = nums[0]
cnt = 0
for num in nums:
if cnt == 0: # 需要更换一个candidate
candidate = num
if num == candidate:
cnt += 1
else:
cnt -= 1
# print(num, candidate, cnt)
return candidate