leetcode 169. 多数元素

方法一：摩尔投票法（Boyer-Moore Voting Algorithm，最优解）

这是解决多数元素问题的经典算法，核心思想是抵消：
候选元素：维护一个候选元素 candidate 和其出现次数 count。
遍历数组：
若当前元素等于 candidate，则 count++。
若当前元素不等于 candidate，则 count–。
若 count 减至 0，则将当前元素设为新的 candidate，并重置 count=1。
最终结果：遍历结束后，candidate 即为多数元素。

三、C++代码实现（方法一：摩尔投票法）

cpp
运行

class Solution {
public:int majorityElement(vector<int>& nums) {int candidate = nums[0];  // 初始候选元素int count = 1;            // 初始计数// 遍历数组for (int i = 1; i < nums.size(); ++i) {if (nums[i] == candidate) {count++;  // 当前元素等于候选元素，计数加1} else {count--;  // 当前元素不等于候选元素，计数减1if (count == 0) {// 计数归零，更换候选元素candidate = nums[i];count = 1;}}}return candidate;  // 最终候选元素即为多数元素}
};

代码解释：

**初始化：**将第一个元素设为候选元素，计数为 1。
遍历数组：
若当前元素等于候选元素，计数加 1。
若当前元素不等于候选元素，计数减 1。
当计数归零，更换候选元素为当前元素，并重置计数为 1。
返回结果：最终的候选元素即为多数元素。
四、复杂度分析
时间复杂度：O(n)，只需遍历数组一次。
空间复杂度：O(1)，只使用了常数额外空间。

五、摩尔投票法的数学证明

多数元素存在性：题目保证多数元素出现次数超过 n/2，因此至少存在 n/2 + 1 个相同元素。
抵消过程：
当遇到相同元素时，计数增加。
当遇到不同元素时，计数减少。
由于多数元素的数量超过一半，即使每次都被其他元素抵消，最终也会剩下至少一个多数元素。
正确性：最终的候选元素必然是多数元素，因为其他元素的数量不足以完全抵消多数元素的计数。

摩尔投票法（Boyer-Moore Voting Algorithm）的正确性证明

一、问题前提与算法回顾

• 前提：数组中存在一个元素，其出现次数超过数组长度的一半（即多数元素）。
• 算法核心：通过"抵消"不同元素，最终剩余的候选元素必为多数元素。

二、证明思路

我们将从数学归纳法和元素数量关系两个角度证明算法的正确性。

三、符号定义

• 设数组长度为 n，多数元素为 target，出现次数为 m，则 m > n/2。
• 其他元素统称为 non-target，总出现次数为 k = n - m，则 k < m（因为 m > n/2 ⇒ n - m < m）。

四、证明过程（方法一：元素抵消分析）

1. 抵消的本质
   摩尔投票法的核心是将 target 与 non-target 按顺序两两抵消：

   • 当遇到 target 时，count++（相当于 target 数量+1）。
   • 当遇到 non-target 时，count--（相当于 non-target 与 target 抵消一次）。
   • 当 count=0 时，说明当前段内 target 和 non-target 数量相等，更换候选元素。

2. 关键结论
   由于 m > k，即 target 的数量比 non-target 多，因此所有抵消操作完成后，target 必然有剩余。

3. 形式化推导

   • 假设每次抵消消耗 1 个 target 和 1 个 non-target，则最多可抵消 k 次（因为 non-target 只有 k 个）。
   • 抵消后剩余的 target 数量为 m - k > 0（因为 m > k）。
   • 这些剩余的 target 会在遍历后期维持 count > 0，使 target 成为最终候选。

五、证明过程（方法二：分段归纳法）

1. 数组分段
   将数组按 count=0 的位置分割成若干段，例如：
   [段1][段2]...[段k][剩余段]，其中每段满足：

   • 段内初始 count=0，结束时 count=0。
   • 段内候选元素的数量等于其他元素的数量（因为 count 从 0 开始到 0 结束）。

2. 归纳假设
   假设在每一段中，候选元素不是 target，则段内 target 的数量 ≤ 其他元素的数量。

3. 矛盾推导

   • 若所有段的候选元素都不是 target，则每段中 target 的数量 ≤ 其他元素的数量。
   • 所有段的 target 总数量 ≤ 所有段的其他元素总数量。
   • 但剩余段中 target 必然存在（因为 m > n/2），且剩余段的 count 最终不为 0，候选元素必为 target。
   • 因此，至少存在一段的候选元素是 target，且剩余段中 target 的数量足够维持 count > 0。

六、极端情况验证

1. 情况1：数组全为同一元素

   • 例如 [5,5,5,5]，候选元素始终为 5，count 递增，正确。

2. 情况2：target 与 non-target 交替出现

   • 例如 [2,1,2,1,2]，长度 n=5，m=3 > 5/2。
     • 遍历过程：
       2（count=1）→ 1（count=0，更换候选为 1）→ 2（count=0，更换候选为 2）→ 1（count=1）→ 2（count=2）。
     • 最终候选为 2，正确。

3. 情况3：non-target 集中出现

   • 例如 [1,1,1,2,2,2,2]，n=7，m=4 > 7/2。
     • 前三个 1 作为候选，count=3；遇到 2 时，count=2→1→0，更换候选为 2，后续三个 2 使 count=4，正确。

七、数学归纳法（形式化证明）

1. 基例：当 n=1 时，数组唯一元素即为多数元素，算法正确。

2. 归纳假设：假设对所有长度 < n 的数组，摩尔投票法正确。

3. 归纳步骤：

   • 对于长度为 n 的数组，设最后一次 count=0 出现在位置 i，则前 i+1 个元素中候选元素 x 的数量等于其他元素数量。
   • 剩余数组 nums[i+1...n-1] 中，target 的数量仍超过半数（因为前 i+1 段中 target 数量 ≤ 其他元素数量，而总 m > n/2，故剩余段中 m' = m - m1 > (n - (i+1))/2）。
   • 根据归纳假设，剩余数组的多数元素为 target，即最终候选元素正确。

八、结论

摩尔投票法的正确性本质源于多数元素的数量优势：当存在一个元素出现次数超过一半时，任何"两两抵消"的操作都无法完全消除该元素，最终剩余的元素必然是多数元素。该算法通过线性遍历和常数空间，高效地利用了这一数学性质，成为解决多数元素问题的最优解法。