LeetCode-Go 题解：229. Majority Element II —— Boyer-Moore 多数投票算法求出现次数超过 n/3 的元素
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本篇文章围绕 LeetCode 第 229 题 Majority Element II（求数组中出现次数超过 ⌊n/3⌋ 的所有元素）展开，以 0229 题解文档 为核心骨架，并结合仓库中 229 题 Go 实现 与 单元测试 进行源码级佐证。读完本文，你将掌握：为什么超过 ⌊n/3⌋ 的元素至多只有两个、如何把经典的 Boyer-Moore 多数投票算法从“找 1 个众数”扩展为“找 2 个候选者”，以及如何在 O(n) 时间、O(1) 空间内一次性筛出全部答案。
题目描述
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
题目大意：给定一个大小为 n 的整数数组，找出其中所有出现次数超过 ⌊ n/3 ⌋ 次的元素。算法要求时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1：
Input: [3,2,3] Output: [3]示例 2：
Input: [1,1,1,3,3,2,2,2] Output: [1,2]解题思路
与 169 题的关系：从“1 个众数”到“2 个候选者”
本题是 169. Majority Element（找出现次数大于 ⌊n/2⌋ 的众数）的加强版，采用的算法是Boyer-Moore Majority Vote Algorithm（摩尔投票算法）的扩展版。
先回顾 169 题的核心思想：数组中超过一半的元素，可以与所有其他元素“一对一抵消”后仍然存活。因此维护一个候选者和一个计数器，遍历数组时计数为 0 就换候选人，相同则 +1、不同则 -1，最终剩下的候选者即为众数。仓库中 169 题的 解法一实现 正是这一思想的直接体现：
// 解法一 时间复杂度 O(n) 空间复杂度 O(1) func majorityElement(nums []int) int { res, count := nums[0], 0 for i := 0; i < len(nums); i++ { if count == 0 { res, count = nums[i], 1 } else { if nums[i] == res { count++ } else { count-- } } } return res }而 229 题把阈值从 ⌊n/2⌋ 降到 ⌊n/3⌋，问题结构发生了质变：
- 超过 ⌊n/2⌋ 的元素至多存在 1 个，所以 169 题只需维护 1 个候选者；
- 超过 ⌊n/3⌋ 的元素至多存在 2 个——因为若有 3 个元素都超过 n/3，它们出现次数之和将大于 n，与总和为 n 矛盾。源码注释精确地表达了这一推导：
// since we are checking if a num appears more than 1/3 of the time // it is only possible to have at most 2 nums (>1/3 + >1/3 = >2/3)因此算法需要同时维护两个候选者 candidate1、candidate2 和两个计数器 count1、count2，这就是 Boyer-Moore 投票算法的扩展形式。
扩展投票：双候选者的三阶段流程
仓库中 229. Majority Element II.go 的解法一完整实现了该算法，整个流程分为三个阶段：
阶段一：选举候选者（Select Candidates）
遍历数组，对每个元素 num 依次判断：
- 若
num == candidate1，则count1++； - 否则若
num == candidate2，则count2++； - 否则若
count1 <= 0，说明候选者 1 已“弹尽粮绝”，把candidate1替换为 num，重置count1 = 1； - 否则若
count2 <= 0，同理替换候选者 2； - 否则两个候选者“双双失血”，
count1--、count2--。
这一阶段结束后，真正超过 ⌊n/3⌋ 的元素一定留在两个候选者之中（因为它的出现次数足以抵消所有其他元素而不被替换掉），但候选者并不一定是答案——由于计数可能被互相抵消，可能出现“没有候选者真正超过 ⌊n/3⌋”的情况，例如数组[1,2,3,4]。
阶段二：重新计数（Recount）
将count1、count2清零，再次遍历数组，分别统计candidate1与candidate2的真实出现次数。这一步是扩展版与 169 题的关键差异：169 题可假定众数必然存在，而本题不能，必须用真实计数做最终裁决。
阶段三：按阈值过滤输出
length := len(nums) if count1 > length/3 && count2 > length/3 { return []int{candidate1, candidate2} } if count1 > length/3 { return []int{candidate1} } if count2 > length/3 { return []int{candidate2} } return []int{}分别判断两个候选者的计数是否严格大于length/3，按情况返回两个、一个或空切片。注意必须严格大于（>），恰好等于 ⌊n/3⌋ 不算答案。
初始值的一个易错细节
实现中初始化为count1, count2, candidate1, candidate2 := 0, 0, 0, 1，即两个候选者初始值不同（0 与 1）。原因在于：若两个候选者初始值相同，当数组第一个元素恰好等于该值时，两个分支会同时命中导致计数混乱。由于题目并未限定元素取值范围，采用两个不同的占位初值可以规避这一边界问题，也无需依赖 nil/哨兵值。
复杂度分析
- 时间复杂度：O(n)。两次线性扫描（选举 + 重新计数），每次都是单层循环，无嵌套。
- 空间复杂度：O(1)。只使用 4 个固定整型变量（两个候选者 + 两个计数器），不随输入规模增长。
- 完全满足题目要求的 linear time 与 O(1) space。
另一种解法：哈希表计数（O(n) 空间）
如果题目没有 O(1) 空间约束，解法二 提供了更直观的哈希表方案：第一遍遍历用map[int]int统计每个元素出现次数，第二遍遍历 map，把计数大于len(nums)/3的键收集进结果切片：
// 解法二 时间复杂度 O(n) 空间复杂度 O(n) func majorityElement229_1(nums []int) []int { result, m := make([]int, 0), make(map[int]int) for _, val := range nums { if v, ok := m[val]; ok { m[val] = v + 1 } else { m[val] = 1 } } for k, v := range m { if v > len(nums)/3 { result = append(result, k) } } return result }该写法在 169 题中同样有对应的 map 计数版实现。它时间上仍为 O(n)，但空间升为 O(n)，可作为理解题意与验证投票算法正确性的参照实现。
单元测试验证
仓库为该题提供了 229. Majority Element II_test.go，覆盖了 4 组典型用例，恰好对应上述所有边界分支：
| 输入 | 预期输出 | 覆盖场景 |
|---|---|---|
[3,2,3] | [3] | 恰好 1 个元素超过 n/3（2/3 次） |
[1,1,1,3,3,2,2,2] | [1,2] | 同时存在 2 个元素超过 n/3 |
[1,2,3,4] | [] | 没有任何元素超过 n/3（返回空切片） |
[2,1,1,1,3] | [1] | 1 出现 3 次 > 5/3，其余均不满足 |
测试驱动方式为表驱动测试（table-driven）：定义question229结构体组合输入para229与期望答案ans229，遍历用例后同时调用majorityElement229与majorityElement229_1两种实现，确保两套解法行为一致。其中[1,2,3,4]这一用例特别有价值——它专门验证了“候选者不一定为答案”的边界：投票阶段会留下两个候选者，但重新计数后发现二者都不达标，最终正确返回空切片。
小结
- 超过 ⌊n/3⌋ 的元素至多两个，这是算法可行性的数学前提；
- Boyer-Moore 投票算法扩展版通过维护双候选者 + 双计数器，在一次线性遍历中完成“候选人筛选”，再用第二次线性遍历做“真实计票”，最终在 O(n) 时间、O(1) 空间内找出全部答案；
- 与 169 题的关键区别在于：169 题众数必然存在可直接返回候选者，而本题必须重新计数验证，因为候选者可能“虚高”；
- 仓库提供了投票版与哈希表版两套实现，并由覆盖 4 种边界情形的表驱动测试保证正确性，可直接参考 实现源码 与 测试源码 深入研读。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
