文章摘要
LCY AI Pro

本文讲解了摩尔投票算法的核心思想，说明了如何在线性扫描中选出多数元素候选人并在必要时二次验证。

摩尔投票算法

摩尔投票算法（Boyer-Moore Majority Vote Algorithm）是一种由 Robert S. Boyer 和 J. Strother Moore 于 1981 年提出的用于在 O(n)O(n) 时间复杂度和 O(1)O(1) 空间复杂度下，寻找数组中出现次数超过一半（大于 n2\frac{n}{2}）的多数元素的有效算法。

算法执行步骤

算法主要分为两个阶段：

阶段1：寻找候选人（Candidate）

我们维护两个变量：candidate（当前候选人）和 count（计数器，初始为 0）。

  • 遍历数组中的每一个元素 x：
    1. 如果 count == 0：说明之前的“战斗”已经平息，此时将 x 设为新的 candidate，并将 count 设为 1。
    2. 如果 count != 0：
      • 如果 x == candidate：说明遇到了盟友，count 加 1。
      • 如果 x ≠\neq candidate：说明遇到了敌人，两人同归于尽，count 减 1。

阶段2：验证候选人（可选）

第一阶段结束后，candidate 仅仅是可能的多数元素。

  • 如果题目保证数组中一定存在多数元素，则直接返回 candidate。
  • 如果题目不确定是否存在多数元素，则需要再次遍历数组，统计 candidate 出现的实际次数。如果次数大于 n2\frac{n}{2}，则它才是真正的多数元素。

算法特点分析

  • 时间复杂度：O(n)O(n)。只需要遍历一次数组（如果需要验证则为两次）。
  • 空间复杂度：O(1)O(1)。只需要两个变量来存储候选人和计数，与输入规模无关。
  • 局限性：只能寻找出现次数 超过一半 的元素。如果目标元素只出现了恰好一半或更少，该算法无法保证结果的正确性。

代码实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def majorityElement(nums):
    # 阶段1：寻找候选人
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
            
    # 阶段2：验证候选人（可选）
    # 如果题目不保证一定存在多数元素，需执行此步
    actual_count = 0
    for num in nums:
        if num == candidate:
            actual_count += 1
            
    if actual_count > len(nums) // 2:
        return candidate
    else:
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

class Solution {
public:
    int majorityElement(std::vector<int>& nums) {
        // 阶段1：寻找候选人
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            // 当计数器为 0 时，更换候选人
            if (count == 0) {
                candidate = num;
                count = 1;
            } 
            // 遇到相同的元素，计数器增加
            else if (num == candidate) {
                count++;
            } 
            // 遇到不同的元素，计数器减少
            else {
                count--;
            }
        }

        // 阶段2：验证候选人（可选）
        // 如果题目不保证数组中一定存在多数元素，则需要手动统计次数
        int actualCount = 0;
        for (int num : nums) {
            if (num == candidate) {
                actualCount++;
            }
        }

        // 检查出现次数是否超过 n / 2
        if (actualCount > nums.size() / 2) {
            return candidate;
        }

        // 若不存在，返回一个特定值（如 -1）或抛出异常
        return -1; 
    }
};

注: C++ 代码省略了main()函数，仅给出摩尔投票算法的实现方式。

总结

摩尔投票算法通过 “抵消” 非多数元素的方式，巧妙地利用了多数元素在数量上的绝对优势。它不需要像哈希表那样消耗额外空间，也不需要像排序那样耗费更多时间，是处理“众数问题”的有效解法之一。