311 lines
10 KiB
Markdown
311 lines
10 KiB
Markdown
---
|
||
tags: [技巧, 摩尔投票, Boyer-Moore, 数组]
|
||
create time: 2026-05-16 18:00
|
||
---
|
||
|
||
# 97-多数元素
|
||
|
||
## 题面
|
||
|
||
> **LeetCode 169. Majority Element**
|
||
|
||
给定一个大小为 `n` 的整数数组，返回其中的**多数元素**。多数元素是指在数组中出现次数 **大于 ⌊ n/2 ⌋** 的元素。
|
||
|
||
**要求：**
|
||
- 线性时间复杂度 $O(n)$
|
||
- 常量额外空间 $O(1)$
|
||
|
||
**假设：**
|
||
- 数组非空
|
||
- 给定的数组**总是存在**多数元素
|
||
|
||
**示例 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`
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
### 先思考一个问题 🤔
|
||
|
||
> 如果一个候选者在选举中获得了超过半数选票，那么在"一票赞成、一票反对"互相抵消的过程中，他还能活到最后吗？
|
||
|
||
> [!tip] 💡 直觉方案
|
||
> 暴力做法是用哈希表统计每个数字的出现次数——但这需要 $O(n)$ 空间。排序后取中间位置的元素可以做到 $O(1)$ 空间但代价是 $O(n \log n)$ 时间。**有没有办法在扫一遍的同时用常数空间找到答案？**
|
||
|
||
### 核心洞察：投票消除法 ⭐
|
||
|
||
多数元素的定义是出现次数 **大于 n/2**。这是一个非常强的条件——意味着它的数量比其他所有元素加起来还多。
|
||
|
||
> [!question] 启发式提问
|
||
> 如果把多数元素想象成"支持票"，其他所有元素加起来是"反对票"。每次拿一张支持票和一张反对票互相抵消，最后剩下来的会是谁？
|
||
|
||
因为多数元素的数量 **> n/2**，即使每一次抵消都恰好消耗一张多数元素的票和一张其他元素的票，多数元素的票也一定会有剩余！
|
||
|
||
这就是 **Boyer-Moore 投票算法** 的核心思想：**维护一个候选者和它的支持计数，遇到相同的就加票，遇到不同的就抵消。**
|
||
|
||
### 算法流程
|
||
|
||
```
|
||
维持两个变量：
|
||
- candidate：当前的"候选人"
|
||
- count：当前候选人的"净票数"
|
||
|
||
遍历数组：
|
||
- 如果 count == 0 → 更换候选人
|
||
- 如果当前元素 == candidate → 加一票（count++）
|
||
- 如果当前元素 != candidate → 抵消一票（count--）
|
||
|
||
最终 candidate 就是多数元素
|
||
```
|
||
|
||
### 逐步跟踪演示
|
||
|
||
以 `nums = [2, 2, 1, 1, 1, 2, 2]` 为例（n=7，多数元素需出现 > 3 次即至少 4 次）：
|
||
|
||
| 步骤 | 读取元素 | 操作 | candidate | count | 解读 |
|
||
|------|---------|------|-----------|-------|------|
|
||
| 初始 | - | 初始化 | `2` | `1` | 第一个元素自动成为候选人 |
|
||
| 1 | `2` | 相同，加票 | `2` | `2` | 二号支持者到来 |
|
||
| 2 | `1` | 不同，抵消 | `2` | `1` | 一敌一消 |
|
||
| 3 | `1` | 不同，抵消 | `1` | `0` | 票归零，候选人更换 |
|
||
| 4 | `1` | count=0，重选 | `1` | `1` | 新候选人上位 |
|
||
| 5 | `2` | 不同，抵消 | `1` | `0` | 又归零了 |
|
||
| 6 | `2` | count=0，重选 | `2` | `1` | 再次更换 |
|
||
|
||
等等——最后的 candidate 是 `2`，正好是正确答案！
|
||
|
||
> [!info] 为什么算法保证正确？
|
||
|
||
设多数元素出现了 $m$ 次，非多数元素共出现 $n-m$ 次，且 $m > n/2$。
|
||
|
||
整个过程中，每次抵消都会同时消耗一张多数元素的票和一张非多数元素的票。最多被抵消的次数是非多数元素的数量 $(n-m)$。因此多数元素剩余的票数至少为：
|
||
|
||
$$m - (n - m) = 2m - n > 0$$
|
||
|
||
所以无论抵消的顺序如何，多数元素永远不可能被完全清除。当 `count` 归零时，更换的候选人不一定是多数元素，但后续的过程会在新的起始点重新累积——**只要后面还有足够的多数元素票就能翻盘**，而根据上面的推导，最终一定能把多数元素推到胜出位置。
|
||
|
||
> [!summary] 🎯 关键结论
|
||
>
|
||
> 多数元素"数量超半"的特性保证了它在任何一对一抵消规则下都是"打不死的小强"。
|
||
|
||
### 流程图
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
Start(["开始<br/>candidate = _, count = 0"]) --> Loop{"有下一个元素?"}
|
||
Loop -- 否 --> Result["返回 candidate ✅"]
|
||
Loop -- 是 --> ZeroCheck{count == 0?}
|
||
ZeroCheck -- 是 --> SetCand["candidate = 当前元素"]
|
||
ZeroCheck -- 否 --> Match{当前元素 == candidate?}
|
||
Match -- 是 --> Inc["count++"]
|
||
Match -- 否 --> Dec["count--"]
|
||
SetCand --> Next
|
||
Inc --> Next
|
||
Dec --> Next
|
||
Next --> Loop
|
||
Result --> End(["结束"])
|
||
```
|
||
|
||
### 备选方案对比
|
||
|
||
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|
||
|------|----------|----------|------|
|
||
| **Boyce-Moore 投票** ⭐ | $O(n)$ | $O(1)$ | 最优解，本题标准答案 |
|
||
| 哈希表计数 | $O(n)$ | $O(n)$ | 直观但空间不达标 |
|
||
| 排序取中位 | $O(n \log n)$ | $O(1)$ 或 $O(\log n)$ | 多数元素一定在 `nums[n/2]` |
|
||
| 随机抽样 | $O(n)$ 期望 | $O(1)$ | 随机选一个数验证，期望很快命中 |
|
||
|
||
> [!note] 📊 为什么排序也能做？
|
||
|
||
既然多数元素出现超过一半，把它排序后放在任意位置，索引 `n/2` 处一定是多数元素。就像超过半数的人穿同一种颜色的衣服站成一排，从中间看去必然是那种颜色。但这不是最优解，仅作面试展示思路广度之用。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
> [!abstract] 📝 Go 伪代码框架
|
||
|
||
```
|
||
candidate := 不存在
|
||
count := 0
|
||
|
||
遍历 nums 中的每个 num:
|
||
如果 count == 0:
|
||
candidate = num
|
||
否则如果 num == candidate:
|
||
count++
|
||
否则:
|
||
count--
|
||
|
||
返回 candidate
|
||
```
|
||
|
||
> [!step] 实现要点
|
||
|
||
1. **count 为零时的处理是最关键的细节**——此时"选举重新开始"，当前元素自动成为新候选人
|
||
2. **不需要最后验证**——题目保证了多数元素一定存在，省去了反证步骤
|
||
3. **一次遍历即可**——不需要像某些变体那样分两阶段
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!summary] 🔑 核心模式记忆
|
||
|
||
```go
|
||
count, candidate := 0, 0
|
||
for _, v := range nums {
|
||
if count == 0 {
|
||
candidate = v
|
||
}
|
||
if v == candidate {
|
||
count++
|
||
} else {
|
||
count--
|
||
}
|
||
}
|
||
return candidate
|
||
```
|
||
|
||
看到 **"出现次数超过 n/k"** + **"O(1) 空间"** → 优先考虑摩尔投票或其推广。
|
||
|
||
### 1. 摩尔投票的思想本质
|
||
|
||
> [!quote] 💬 一句话总结
|
||
>
|
||
> **"少数互抵消，少数扛 majority"** ——让不同的互相消灭，剩下的就是强者。
|
||
|
||
这是一种"去冲突"的思维：不需要知道每个元素的具体频次，只需要关注"相同还是不同"这个相对关系。
|
||
|
||
### 2. 扩展：出现次数 > n/3 的元素
|
||
|
||
当条件放宽到"出现次数超过 n/3"时，最多可能有 **两个** 这样的元素。摩尔投票可以自然地推广到维护**两个候选者**：
|
||
|
||
```go
|
||
func majorityElement(nums []int) []int {
|
||
cand1, cand2, c1, c2 := 0, 0, 0, 0
|
||
|
||
// 第一阶段：选出两个候选人
|
||
for _, v := range nums {
|
||
switch {
|
||
case v == cand1:
|
||
c1++
|
||
case v == cand2:
|
||
c2++
|
||
case c1 == 0:
|
||
cand1, c1 = v, 1
|
||
case c2 == 0:
|
||
cand2, c2 = 1
|
||
default:
|
||
c1--
|
||
c2--
|
||
}
|
||
}
|
||
|
||
// 第二阶段：验证（题目若保证存在可省略）
|
||
var result []int
|
||
threshold := len(nums) / 3
|
||
for _, v := range nums {
|
||
if v == cand1 && c1 > threshold { result = append(result, cand1); break }
|
||
if v == cand2 && c2 > threshold { result = append(result, cand2); break }
|
||
}
|
||
return result
|
||
}
|
||
```
|
||
|
||
> [!warning] ⚠️ n/3 版本的注意事项
|
||
>
|
||
> 与 n/2 版本不同，n/3 版本在第一阶段选出候选者后**必须再进行第二阶段验证**，因为可能存在两个候选者都不是真正的多数元素的情况（数组中没有任何元素真正超过 n/3）。
|
||
|
||
### 3. 关联变体题
|
||
|
||
| 题目 | 变化点 | 核心思路 |
|
||
|------|--------|---------|
|
||
| **169. Majority Element** | 超过 n/2 | 摩尔投票 ✅ |
|
||
| **229. Majority Element II** | 超过 n/3 | 双候选人摩尔投票 |
|
||
| **GCD Sort 类问题** | 按最大出现频率选择 | 摩尔投票的变种应用 |
|
||
|
||
### 4. Go 运行细节
|
||
|
||
> [!example] 🐹 Go 特有注意事项
|
||
|
||
- `count` 和 `candidate` 的初始化值不重要，因为在第一次遍历时 `count == 0` 的条件一定会触发 `candidate = nums[0]`
|
||
- 由于题目保证多数元素存在，无需第二阶段的计数验证——这比严格实现节省了 $O(n)$ 时间和 $O(n)$ 空间
|
||
- 如果想写得更紧凑，可以用 Go 的三元替代（if 表达式）来减少行数，但**可读性优先**
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
// majorityElement returns the majority element using the Boyer-Moore Voting Algorithm.
|
||
// A majority element appears more than ⌊ n/2 ⌋ times.
|
||
// The problem guarantees that a majority element always exists.
|
||
func majorityElement(nums []int) int {
|
||
// ── Step 1: 初始化 ──
|
||
// count 为 0 时，下一次赋值会自动选定第一个候选人
|
||
var candidate, count int
|
||
|
||
// ── Step 2: 投票阶段（一次遍历） ──
|
||
for _, num := range nums {
|
||
if count == 0 {
|
||
// 当前没有候选人（或票数归零），新候选人上任
|
||
candidate = num
|
||
}
|
||
// 投给当前候选人，或者投给别人（抵消）
|
||
if num == candidate {
|
||
count++ // 支持
|
||
} else {
|
||
count-- // 反对
|
||
}
|
||
}
|
||
|
||
// ── Step 3: 返回结果 ──
|
||
// 题目保证多数元素一定存在，无需二次验证
|
||
return candidate
|
||
}
|
||
```
|
||
|
||
### 代码走读
|
||
|
||
> [!success] ✅ 复杂度总结
|
||
|
||
| 指标 | 结果 | 说明 |
|
||
|------|------|------|
|
||
| **时间复杂度** | $O(n)$ | 仅需一次线性扫描 |
|
||
| **空间复杂度** | $O(1)$ | 仅使用了两个整型变量 `candidate` 和 `count` |
|
||
|
||
完美满足题目的进阶要求！
|
||
|
||
> [!quote] 💬 面试建议
|
||
|
||
这道题是摩尔投票算法最经典的入门题。面试中被问到后：
|
||
1. **先阐述暴力解法**（哈希表 / 排序），展示你能想到多种方案
|
||
2. **引出"有没有 O(1) 空间的解法"**，自然过渡到摩尔投票
|
||
3. **手绘流程图**解释"抵消"过程，展现你的思路清晰程度
|
||
4. **证明正确性**——简要说明多数元素因数量过半而不可能被完全消除
|
||
5. **提及扩展到 n/3**——展示你对这个算法的理解不止于表面
|
||
|
||
> [!warning] ⚠️ 常见陷阱
|
||
|
||
> 1. **忘记处理 `count == 0` 的情况**——这是换候选人时机，漏掉会导致错误
|
||
> 2. **把 `==` 写成 `!=` 导致逻辑反转**——仔细检查条件分支
|
||
> 3. **不加验证地用于不保证存在的场景**——实际工程中应该增加第二阶段验证
|