wonder/leetcode-go

Fork 0

Files

T

wonder 9067e29acb vault backup: 2026-05-16 14:10:20

2026-05-16 14:10:21 +08:00

10 KiB

Raw Permalink Blame History

tags, create time

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] 🎯 关键结论

多数元素"数量超半"的特性保证了它在任何一对一抵消规则下都是"打不死的小强"。

流程图

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] 实现要点

count 为零时的处理是最关键的细节——此时"选举重新开始"，当前元素自动成为新候选人
不需要最后验证——题目保证了多数元素一定存在，省去了反证步骤
一次遍历即可——不需要像某些变体那样分两阶段

技巧

[!summary] 🔑 核心模式记忆

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"时，最多可能有两个这样的元素。摩尔投票可以自然地推广到维护两个候选者：

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 表达式）来减少行数，但可读性优先

代码

// 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] 💬 面试建议

这道题是摩尔投票算法最经典的入门题。面试中被问到后：

先阐述暴力解法（哈希表 / 排序），展示你能想到多种方案
引出"有没有 O(1) 空间的解法"，自然过渡到摩尔投票
手绘流程图解释"抵消"过程，展现你的思路清晰程度
证明正确性——简要说明多数元素因数量过半而不可能被完全消除
提及扩展到 n/3——展示你对这个算法的理解不止于表面

[!warning] ⚠️ 常见陷阱

忘记处理 count == 0 的情况——这是换候选人时机，漏掉会导致错误

把 == 写成 != 导致逻辑反转——仔细检查条件分支

不加验证地用于不保证存在的场景——实际工程中应该增加第二阶段验证

10 KiB Raw Permalink Blame History Unescape Escape