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. **不加验证地用于不保证存在的场景**——实际工程中应该增加第二阶段验证
|