企业官网建设流程全解析

• 示例工程

本文以 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⌋，满足条件的元素可能不止一个；
• 答案不保证存在：可能出现零个或两个答案，因此扫描结束后的候选值必须经过二次校验才能进入结果集。

三个官方示例

数据范围与进阶要求

• 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. 多数元素 中，单候选版本维护一个计数器，不同元素两两抵消，多数元素因其数量优势最终存活；本题则需要维护两个计数器，每遇到三个互不相同的元素时三票互相抵消一次。

流程分为两个阶段：

1. 第一趟（候选生成）：维护候选值m1、m2及其计数n1、n2，按以下优先级更新——
   • 当前元素m等于m1或m2时，对应计数+1；
   • 否则若某个计数为 0，则用当前元素替换该候选并置计数为 1；
   • 否则（两个计数都为正且m与两个候选都不同），n1、n2同时-1（三元素互相抵消）。
2. 第二趟（候选验证）：由于答案不保证存在，必须重新遍历数组统计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 Python3

class 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 Java

class Solution { public List<Integer> 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; } } List<Integer> 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 C++

class Solution { public: vector<int> majorityElement(vector<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; } } vector<int> 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 Go

func 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 IList<int> 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 List<int>(); 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 语言实现小结

五、算法正确性论证

候选覆盖性：设真实答案集合为 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 个互不相同的元素即整体抵消一次，最后统一验证。

通用性小结

1. 先由鸽巢原理确定答案数量上界（⌊n/k⌋对应至多 k-1 个）；
2. 第一趟并行维护 k-1 个候选与计数，不同元素配对抵消；
3. 第二趟精确统计候选频率，严格大于阈值才入选。

掌握这一模式，即可应对「多数元素」系列题目的全部变体。

参考与延伸阅读（均在当前仓库内）

• 本题完整题解与六语言代码：solution/0200-0299/0229.Majority Element II/README.md
• 独立源码文件：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.cs、Solution.php
• 摩尔投票单候选人基础题：169. 多数元素题解

• 示例工程