LeetCode 229「多数元素 II」多语言题解：Boyer-Moore 摩尔投票算法进阶实战（doocs/leetcode）

示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 仓库中 229. 多数元素 II 题解 为主体系统讲解「找出数组中出现次数超过 ⌊n/3⌋ 的元素」这一经典进阶问题从数学上论证答案至多两个推导哈希计数与摩尔投票两条路线并给出仓库内 Python3、Java、C、Go、C#、PHP 六种语言的完整实现与逐行剖析。读完本文你将掌握双候选人摩尔投票的通用模式并能独立写出时间复杂度 O(n)、空间复杂度 O(1) 的解法。一、题目概述从「多数元素」到「多数元素 II」给定一个大小为n的整数数组nums找出其中所有出现次数超过⌊n / 3⌋的元素。这与经典的 169. 多数元素阈值⌊n/2⌋且保证存在相比有两个本质变化阈值更低从⌊n/2⌋降为⌊n/3⌋满足条件的元素可能不止一个答案不保证存在可能出现零个或两个答案因此扫描结束后的候选值必须经过二次校验才能进入结果集。三个官方示例示例输入输出说明示例 1nums [3,2,3][3]n 3⌊n/3⌋ 13 出现 2 次 1示例 2nums [1][1]n 1⌊n/3⌋ 01 出现 1 次 0示例 3nums [1,2][1,2]n 2⌊n/3⌋ 01 和 2 各出现 1 次均 0数据范围与进阶要求1 nums.length 5 * 10^4-10^9 nums[i] 10^9元素可为任意整数初始候选值需谨慎选取进阶设计时间复杂度 O(n)、空间复杂度 O(1) 的算法。数据规模达到 5 万级别且元素值范围覆盖 20 亿这直接否定了「开一个大数组计数」的做法也意味着朴素哈希表O(n) 空间可以解决问题但进阶路线必须走向摩尔投票Boyer-Moore Voting。二、核心数学结论答案为什么至多两个设数组长度为 n若存在三个互不相同的元素其出现次数都严格大于⌊n/3⌋则三者出现次数之和至少为3 × (⌊n/3⌋ 1) n这与「三个元素的总出现次数不可能超过数组长度 n」矛盾。因此出现次数超过 ⌊n/3⌋ 的元素至多存在两个。这一结论是双候选人摩尔投票成立的前提我们只需要同时维护两个候选值及其计数器一轮扫描后候选值集合必然覆盖所有真实答案随后用第二趟扫描精确核实即可。三、解法路线对比3.1 路线一哈希表计数直观O(n) 空间遍历数组用哈希表统计每个元素出现次数凡是次数大于⌊n/3⌋的元素即加入答案。思路最直白但空间复杂度为 O(n)不满足进阶要求。仓库中 PHP 版本的 Solution.php 正是这一路线的实现——它是本题多语言解法中唯一采用哈希计数的版本class Solution { /** * param Integer[] $nums * return Integer[] */ function majorityElement($nums) { $rs []; $n count($nums); for ($i 0; $i $n; $i) { $hashmap[$nums[$i]] 1; if ($hashmap[$nums[$i]] $n / 3) { array_push($rs, $nums[$i]); } } return array_unique($rs); } }实现要点单趟遍历中边计数边判断一旦某元素计数突破n / 3立即入结果数组同一元素可能在多个位置首次突破阈值因此结尾用array_unique($rs)去重时间 O(n)空间 O(n)哈希表。PHP 没有显式类型约束$hashmap[$nums[$i]] 1对不存在的键自动从 0 累加写法简洁。3.2 路线二Boyer-Moore 摩尔投票进阶O(1) 空间核心思想将「不同元素相互抵消」的配对逻辑推广到两个候选席位。在 169. 多数元素 中单候选版本维护一个计数器不同元素两两抵消多数元素因其数量优势最终存活本题则需要维护两个计数器每遇到三个互不相同的元素时三票互相抵消一次。流程分为两个阶段第一趟候选生成维护候选值m1、m2及其计数n1、n2按以下优先级更新——当前元素m等于m1或m2时对应计数1否则若某个计数为 0则用当前元素替换该候选并置计数为 1否则两个计数都为正且m与两个候选都不同n1、n2同时-1三元素互相抵消。第二趟候选验证由于答案不保证存在必须重新遍历数组统计m1、m2的真实出现次数只有次数严格大于⌊n/3⌋的候选才加入结果。这一「先抵消、后验证」的两趟结构与 169 题「题目保证存在多数元素、一趟即可返回」形成鲜明对照——在仓库的 169 题 README 中明确指出由于题目已保证存在多数值第一次遍历结束后直接返回候选值即可无需二次确认而 229 题必须补上验证环节。四、六语言实现与逐行剖析仓库 0229.Majority Element II 提供了 Python3、Java、C、Go、C#、PHP 六种语言的完整实现README 中的代码与目录下各Solution.*文件完全一致如 Solution.py、Solution.java、Solution.go 等可直接复制运行。4.1 Python3class Solution: def majorityElement(self, nums: List[int]) - List[int]: n1 n2 0 m1, m2 0, 1 for m in nums: if m m1: n1 1 elif m m2: n2 1 elif n1 0: m1, n1 m, 1 elif n2 0: m2, n2 m, 1 else: n1, n2 n1 - 1, n2 - 1 return [m for m in [m1, m2] if nums.count(m) len(nums) // 3]剖析初始候选m1, m2 0, 1刻意取两个互不相同的占位值。由于元素值范围为[-10^9, 10^9]0 与 1 不可能同时被否决且第一趟中一旦某计数归零就会被真实元素替换因此占位值不会污染最终结果第二趟用nums.count(m)统计真实频率与len(nums) // 3比较注意 Python 的//是向下取整除法⌊n/3⌋与之精确对应列表推导式天然完成「验证 收集」m1、m2至多两个即使相同也会被count与阈值正确过滤。4.2 Javaclass Solution { public ListInteger majorityElement(int[] nums) { int n1 0, n2 0; int m1 0, m2 1; for (int m : nums) { if (m m1) { n1; } else if (m m2) { n2; } else if (n1 0) { m1 m; n1; } else if (n2 0) { m2 m; n2; } else { --n1; --n2; } } ListInteger ans new ArrayList(); n1 0; n2 0; for (int m : nums) { if (m m1) { n1; } else if (m m2) { n2; } } if (n1 nums.length / 3) { ans.add(m1); } if (n2 nums.length / 3) { ans.add(m2); } return ans; } }剖析第一趟结束后显式将n1、n2重置为 0再开启第二趟独立统计避免复用抵消后的残留计数第二趟统计时使用else if分支——若m1 m2极端情况下二者指向同一候选每个元素只计一次保证频率统计的准确性验证阈值使用整数除法nums.length / 3与⌊n/3⌋语义一致。4.3 Cclass Solution { public: vectorint majorityElement(vectorint nums) { int n1 0, n2 0; int m1 0, m2 1; for (int m : nums) { if (m m1) n1; else if (m m2) n2; else if (n1 0) { m1 m; n1; } else if (n2 0) { m2 m; n2; } else { --n1; --n2; } } vectorint ans; if (count(nums.begin(), nums.end(), m1) nums.size() / 3) ans.push_back(m1); if (count(nums.begin(), nums.end(), m2) nums.size() / 3) ans.push_back(m2); return ans; } };剖析第二趟复用标准库algorithm的std::count对区间[begin, end)统计候选出现次数代码量最精简注意m1、m2可能相同例如数组全为同一元素时此时第一个count(m1)已覆盖该元素的真实频率第二个count(m2)因频率相同不会重复入结果push_back前的严格大于判断天然去重时间复杂度 O(n)std::count额外消耗 O(n) 但整体仍为线性空间 O(1)。4.4 Gofunc majorityElement(nums []int) []int { var n1, n2 int m1, m2 : 0, 1 for _, m : range nums { if m m1 { n1 } else if m m2 { n2 } else if n1 0 { m1, n1 m, 1 } else if n2 0 { m2, n2 m, 1 } else { n1, n2 n1-1, n2-1 } } n1, n2 0, 0 for _, m : range nums { if m m1 { n1 } else if m m2 { n2 } } var ans []int if n1 len(nums)/3 { ans append(ans, m1) } if n2 len(nums)/3 { ans append(ans, m2) } return ans }剖析与 Java 版结构完全对称第一趟生成候选第二趟重置计数后验证用append惰性构建结果切片len(nums)/3为整数除法语义与⌊n/3⌋一致Go 的零值初始化使var n1, n2 int天然从 0 开始无需显式赋值。4.5 C#public class Solution { public IListint MajorityElement(int[] nums) { int n1 0, n2 0; int m1 0, m2 1; foreach (int m in nums) { if (m m1) { n1; } else if (m m2) { n2; } else if (n1 0) { m1 m; n1; } else if (n2 0) { m2 m; n2; } else { --n1; --n2; } } var ans new Listint(); ans.Add(m1); ans.Add(m2); return ans.Where(m nums.Count(n n m) nums.Length / 3).ToList(); } }剖析第二趟用 LINQ 的nums.Count(n n m)统计频率配合Where(...).ToList()一步完成验证与收集ans先无差别加入m1、m2再由Where过滤出真正超过⌊n/3⌋的元素若两候选相同Distinct语义由过滤条件隐式保证频率相同则至多一个通过阈值。4.6 语言实现小结语言第二趟验证方式特点Python3nums.count(m) 列表推导式最简洁两趟合并为一行Java重置计数后显式二次循环结构最直白适合教学Cstd::count(begin, end, m)复用标准库代码量最小Go重置计数后显式二次循环与 Java 对称零值初始化C#LINQCountWhere函数式风格声明式过滤PHP哈希表计数 array_unique唯一走 O(n) 空间的路线五、算法正确性论证候选覆盖性设真实答案集合为 S|S| ≤ 2见第二节论证。第一趟扫描中若m1、m2都已被真实答案占据则每当遇到与二者都不同的元素 x会执行--n1; --n2相当于用一个 x 同时抵消两个真实答案的票。由于每个真实答案出现次数严格大于⌊n/3⌋两个真实答案合计贡献超过2⌊n/3⌋票而所有非答案元素至多n - 2(⌊n/3⌋1) 2⌊n/3⌋个不足以将两个候选同时清零。因此第一趟结束时m1、m2一定覆盖真实答案。验证必要性候选值仅保证「可能是答案」不保证「一定是答案」。若数组根本不存在超过⌊n/3⌋的元素如nums [1,2,3]第一趟仍会产出两个候选但它们都不满足阈值。这正是本题与 169 题的关键差异——必须增加第二趟严格验证。边界情形验证nums [3,2,3]⌊3/3⌋1。第一趟后候选为 3计数 1与 2计数 1第二趟统计得到 3 出现 2 次、2 出现 1 次仅 3 通过输出[3]✓nums [1]⌊1/3⌋0。候选 1 出现 1 次 0输出[1]✓nums [1,2]⌊2/3⌋0。1 与 2 各出现 1 次均 0输出[1,2]✓nums [1,2,3]⌊3/3⌋1。三个元素各出现 1 次均不满足 1输出[]✓。六、复杂度分析与延伸思考复杂度时间复杂度O(n)。第一趟单次遍历 O(n)第二趟验证 O(n)总耗时 2n 仍为线性空间复杂度O(1)。仅使用两个候选值与两个计数器的常数空间PHP 哈希版本除外其空间为 O(n)。与 169 题的对照学习建议将本文与仓库内 169. 多数元素摩尔投票法 对照阅读169 题是单候选人、一趟即可返回题目保证答案存在229 题是双候选人、必须两趟答案可能不存在。二者的「候选生成 计数抵消」逻辑一脉相承229 题可视为对 169 题摩尔投票思想在阈值1/k情形下的自然推广——若要找出现次数超过⌊n/k⌋的元素可维护 k-1 个候选值每遇到 k 个互不相同的元素即整体抵消一次最后统一验证。通用性小结先由鸽巢原理确定答案数量上界⌊n/k⌋对应至多 k-1 个第一趟并行维护 k-1 个候选与计数不同元素配对抵消第二趟精确统计候选频率严格大于阈值才入选。掌握这一模式即可应对「多数元素」系列题目的全部变体。参考与延伸阅读均在当前仓库内本题完整题解与六语言代码solution/0200-0299/0229.Majority Element II/README.md独立源码文件Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.cs、Solution.php摩尔投票单候选人基础题169. 多数元素题解赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode-Go 题解229. Majority Element II —— Boyer-Moore 多数投票算法求出现次数超过 n/3 的元素LeetCode Go 题解229. Majority Element II —— Boyer Moore 多数投票算法求出现次数超过 n/3 的元素 导读示例工程LeetCode 0169 Majority Element用 Go 实现 Boyer-Moore 多数投票算法LeetCode 0169 Majority Element用 Go 实现 Boyer Moore 多数投票算法 导读 本文以 LeetCode 第 169示例工程LeetCode-Go 题解精讲169. Majority Element 的 Boyer-Moore 多数投票算法LeetCode Go 题解精讲169. Majority Element 的 Boyer Moore 多数投票算法 导读 本文围绕 LeetCode 第 1示例工程上一篇HelloAgents Code Agent 补丁落盘机制实战解析从一条「Patch applied」Action 笔记看懂安全文件修改的完整链路下一篇Manim v0.17.2 版本解析OpenGL Surface 初始化修复、CodeQL 安全扫描与 CI 升级创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考