跳至主要內容

多数元素：Boyer-Moore投票算法的数学证明

老张2026/4/30大约 7 分钟

多数元素：Boyer-Moore投票算法的数学证明

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约18分钟 | 难度：Easy

开篇故事

这道题是 Easy，但藏着一个我觉得非常漂亮的算法——Boyer-Moore 投票算法。这个算法我第一次看到的时候，花了将近半个小时才真正理解它的正确性证明。

它的逻辑是这样的：想象一个选举，候选人 A 的得票超过总票数的一半。现在随机找出两个投票不同的人，让他们互相"抵消"（双双离场）。最后留下来的人，一定都是支持同一个候选人的。

为什么？因为候选人 A 的票数 > n/2，其他所有候选人的票数合计 < n/2。每次抵消，A 最多丢失一票，对手也丢失一票。当所有对手的票被消光时，A 还剩票，因为 A 的票比对手多。

这个直觉清晰了，但代码实现更巧妙——用一个变量 candidate 和一个计数器 count，不需要真正"找两张不同的票互相消除"。

一、题目解析

LeetCode 169. 多数元素（Majority Element）

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

输入输出示例：

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

边界情况 3（全相同元素）：

输入：nums = [1,1,1]
输出：1

边界情况 4（单元素）：

输入：nums = [5]
输出：5

考察的核心知识点：

  • 哈希表统计频次
  • 排序后取中值
  • Boyer-Moore 投票算法的 O(n) O(1) 实现
  • 数学证明（为什么这个算法是正确的）

二、解法一：哈希表统计

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.merge(num, 1, Integer::sum);
            if (count.get(num) > nums.length / 2) return num;
        }
        throw new IllegalStateException("No majority element");
    }
}

时间复杂度：O(n)，空间复杂度：O(n)。

三、解法二：排序取中值

排序后，下标 n/2 处的元素一定是多数元素（因为多数元素超过半数，无论怎么排列，中间位置一定是多数元素）。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

时间复杂度：O(n log n)，空间复杂度：O(log n)（快排栈）。

四、解法三：Boyer-Moore 投票算法

完整数学证明

算法：

  • 维护 candidate（当前候选人）和 count（候选人的"净票数"）
  • 遍历每个元素：
    • 如果 count == 0，用当前元素替换 candidate，count = 1
    • 如果当前元素 == candidate，count++（支持票）
    • 如果当前元素 != candidate，count--（抵消一票）
  • 最终 candidate 就是多数元素

证明多数元素一定最终成为候选人：

设多数元素为 m，出现次数为 k，其中 k > n/2。

每次 count 减少时，必然是 m 和某个非 m 元素互相抵消（count-- 对应一个 "m 的失票" 或 "非 m 的失票"）。

更精确地分析：当最终的 candidate 是非 m 元素时，这个 candidate 的"净票数" count > 0，意味着它比所有被它抵消的元素出现得多。但 m 是多数元素，它不可能被任何其他单一元素完全抵消——m 有 k > n/2 票，非 m 元素合计只有 n-k < n/2 票，不够把 m 全部抵消。所以，最终 candidate 不可能是非 m 元素。

更直觉化：每次 count-- 都是一个 "m 对一个非 m" 或 "非 m 对一个非 m" 的对消，最多 k 次 "m 对非 m" 的对消（消耗 m 的所有票），但非 m 元素总共只有 n-k < k 票，不够消耗完 m 的所有票。所以 m 一定有剩余，最终成为 candidate。

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                // 上一个候选人被完全抵消，换新候选人
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                // 支持当前候选人
                count++;
            } else {
                // 反对当前候选人，互相抵消
                count--;
            }
        }
        
        // 题目保证多数元素存在，所以不需要验证 candidate
        // 如果题目不保证，需要再扫描一遍确认 candidate 的频次 > n/2
        return candidate;
    }
}

时间复杂度：O(n)，一次遍历。

空间复杂度：O(1)，只用两个变量。

我在 LeetCode 提交，运行时间 1ms，击败 99.8% 的 Java 用户。

五、举一反三

同类型题目

LeetCode 229. 多数元素 II

找出出现次数 > n/3 的所有元素（最多 2 个）。Boyer-Moore 投票算法扩展：维护两个候选人和两个计数器，找出现次数 > n/3 的候选人，然后再扫描一遍确认频次。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0, cand2 = 0, count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
            else if (count1 == 0) { cand1 = num; count1 = 1; }
            else if (count2 == 0) { cand2 = num; count2 = 1; }
            else { count1--; count2--; }
        }
        
        // 验证两个候选人的真实频次
        count1 = count2 = 0;
        for (int num : nums) {
            if (num == cand1) count1++;
            else if (num == cand2) count2++;
        }
        
        List<Integer> result = new ArrayList<>();
        if (count1 > nums.length / 3) result.add(cand1);
        if (count2 > nums.length / 3) result.add(cand2);
        return result;
    }
}

LeetCode 1150. 检查一个数是否在数组中占绝大多数（付费题）

判断某个特定数字在数组中是否出现超过一半次数。用二分查找在已排序数组里找该数字的出现范围。

六、踩坑实录

坑一：Boyer-Moore 算法结束后必须验证（在没有多数元素保证时）

现象： 对没有多数元素的数组（如 [1, 2, 3]）调用算法，结果是 3（最后一个元素），但没有任何元素出现超过一半。

原因： Boyer-Moore 算法保证了：如果多数元素存在，最终 candidate 一定是它。但如果多数元素不存在，candidate 是什么完全不确定。

解法： 本题题目保证多数元素存在，不需要验证。但如果是 LeetCode 229 或其变体，算法结束后必须再扫描一遍确认 candidate 的实际频次 > n/k。

坑二：count 初始化时机

现象： 写法把 count 初始化为 0，然后直接进入循环，导致第一个元素进来时 count==0，触发了候选人替换，但 candidate 还没初始化。

原因： 初始化顺序问题。

// 方法一：先处理第一个元素
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) { ... }

// 方法二：统一处理
int candidate = 0, count = 0;
for (int num : nums) {
    if (count == 0) { candidate = num; count = 1; }
    else if (num == candidate) count++;
    else count--;
}

两种写法都对，用第二种时注意第一个 if 和后面两个是 else if，不要漏了 else。

坑三：多数元素 II 中两个候选人的更新顺序

现象： LeetCode 229 中，某些输入下两个候选人有一个没有被正确识别。

原因： 在更新时，先检查是否等于某个候选人，再检查 count 是否为 0，这个顺序很关键。如果一个数等于 cand1，就不应该再参与 cand2 的候选判断，否则同一个数可能被当成两个不同的候选人参与计数。

七、总结

Boyer-Moore 投票算法以极简的代码（两个变量，一次遍历）解决了一个看似需要 O(n) 空间的问题。理解它的关键在于"抵消"的数学意义，不是随意的配对，而是有严格的代数保证。

三条核心要点：

  1. Boyer-Moore 的核心逻辑：当 count 降为 0 时，意味着之前的 candidate 和等量的"反对票"互相消光了，此时换新候选人。最终留下的 candidate 就是"被消光最慢的那个"，由多数元素的频次保证它一定能存活。

  2. 如果题目不保证多数元素存在，算法结束后必须再验证 candidate 的实际频次是否满足条件。

  3. 扩展到"出现次数 > n/k"：维护 k-1 个候选人，每次发现完全不同的 k 个元素就互相抵消，最终留下的不超过 k-1 个候选人中筛选出真正满足条件的。

延伸思考：

Boyer-Moore 算法的"投票抵消"思想在分布式系统里有应用：在分布式共识中，如果一个候选 leader 得到了超过半数节点的支持，任何对它的反对方案（因为少数派）最终都会被"投票"压制。

编辑此页
最近更新:
贡献者: xiaozhangge