169. 多数元素 (Easy)
专题归类： 12-技巧 LeetCode 链接： https://leetcode.cn/problems/majority-element/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
题目详细分析
数据范围： n == nums.length，1 <= n <= 5 * 10^4，-10^9 <= nums[i] <= 10^9
核心约束：
- 多数元素定义为出现次数大于
⌊n/2⌋（不是”大于等于”，不是”等于”） - 题目保证一定存在多数元素，无需二次验证
- 数组非空
关键洞察：
- 多数元素出现次数超过总数的一半，这意味着：多数元素的个数 > 其他所有元素个数的总和
- 这个性质非常强——一个多数元素可以”抵消”掉所有其他元素后还有剩余
- 这引出了 Boyer-Moore 投票算法：维护一个候选，遇到相同就 +1，不同就 -1，归零就换候选
- 也可以用分治法、排序法、哈希表法，但投票法是最优的 O(1) 空间解法
小白版直白理解
就像班级选班长，每个同学投一票，得票数超过全班人数一半的人当选。
有个很聪明的计票方式：不同票相互抵消。想象一下，你让所有投不同票的人两两组队互相抵消，到最后还剩下来的人，就是得票超过半数的人。
具体来说：
- 你先随便选一个人当”候选人”
- 每看到一票投给他，就给他加一分
- 每看到一票投给别人，就给他减一分
- 当他的分数归零时，换成当前这票的人当候选人
- 最后剩下的候选人就是班长
因为多数票超过了半数，所以不管怎么抵消，最后留下的一定是它。
解题思路
思路一：Boyer-Moore 投票算法（推荐）
思路讲解： 核心思想是”正负抵消”。维护两个变量：
candidate：当前候选的多数元素count：候选元素的”净胜票数”
遍历数组：
- 如果
count == 0，将当前元素设为新的候选人 - 如果当前元素 ==
candidate，则count += 1 - 否则
count -= 1
为什么正确？ 多数元素出现次数超过一半，所以它的净胜票数一定为正。无论其他元素如何”围攻”，多数元素最终一定能保持为正。
def majorityElement(nums):
candidate = 0
count = 0
for num in nums:
if count == 0: # 当前候选被"抵消"完，更换候选
candidate = num
# 投票：相同 +1，不同 -1
count += 1 if num == candidate else -1
return candidate时间复杂度： O(n) | 空间复杂度： O(1)
思路二：排序法
思路讲解： 将数组排序后，多数元素一定会出现在数组的中间位置（下标 n // 2），因为它的出现次数超过一半。这是最直观的解法之一。
def majorityElement(nums):
nums.sort()
return nums[len(nums) // 2]时间复杂度： O(n log n)（排序） | 空间复杂度： O(1) 或 O(n)（取决于排序算法）
思路三：哈希表计数
思路讲解： 用哈希表统计每个元素的出现次数，找到出现次数 > ⌊n/2⌋ 的元素。思路最直接，但使用了额外空间。
def majorityElement(nums):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
if count[num] > len(nums) // 2:
return num时间复杂度： O(n) | 空间复杂度： O(n)
思路四：分治法
思路讲解： 递归地将数组分成左右两半，分别求出左半和右半的多数元素，然后在合并时做最终决策：
- 如果左右多数元素相同，直接返回
- 如果不同，分别数它们在合并数组中的出现次数，选出现多的那个
def majorityElement(nums):
def majority(l, r):
if l == r:
return nums[l]
mid = (l + r) // 2
left = majority(l, mid)
right = majority(mid + 1, r)
if left == right:
return left
left_cnt = sum(1 for i in range(l, r + 1) if nums[i] == left)
right_cnt = sum(1 for i in range(l, r + 1) if nums[i] == right)
return left if left_cnt > right_cnt else right
return majority(0, len(nums) - 1)时间复杂度： O(n log n) | 空间复杂度： O(log n)（递归栈）
易错点
- 题目保证存在多数元素：如果不保证，Boyer-Moore 算法得到的
candidate需要再遍历一次验证是否真的 >⌊n/2⌋ count归零时的处理：if count == 0: candidate = num，然后下一句应该是count += 1（因为当前票投给了新候选人）。在实现中需要注意不要写反顺序⌊n/2⌋的理解：长度为 7 的数组，⌊7/2⌋ = 3，多数元素出现次数至少为 4；长度为 8，⌊8/2⌋ = 4，出现次数至少为 5- 只有一个元素的情况：直接返回该元素
- 排序法的陷阱：排序后取
nums[n // 2]成立的前提是多数元素存在，否则不成立
框架提炼
Boyer-Moore 投票算法模板：找出现次数超过一半的元素
def findMajority(nums):
candidate = 0
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate如果需要验证（题目不保证一定存在）：
def findMajority(nums):
candidate = 0
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# 验证阶段
cnt = sum(1 for num in nums if num == candidate)
return candidate if cnt > len(nums) // 2 else -1核心思想： “正负抵消”——多数元素可以抵消所有其他元素后仍有剩余。这种思想类似于：
- 不同元素的相互抵消
- 配对消除问题
- 寻找占绝对优势的元素
关联题目
- 229-多数元素II — 找出现次数 >
⌊n/3⌋的元素（最多两个），扩展投票算法维护两个候选 - 136-只出现一次的数字 — 同样是”配对消除”思想，但用异或而非投票
- 1150-检查一个数是否在数组中占绝大多数 — 二分查找判断某元素是否 >
⌊n/2⌋ - 169-多数元素 和 229-多数元素II 构成了 Boyer-Moore 投票算法的完整应用场景