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)。示例 1Input: [3,2,3] Output: [3]示例 2Input: [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/32/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），仅供参考