摩尔投票法详解

版本 2 简化版（假设数组一定存在绝对众数，笔试常用）

如果题目明确说明「数组中一定存在绝对众数」，可以省略验证阶段，直接返回候选值：

def majority_element_simple(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

测试案例 可直接运行

# 测试 1：存在绝对众数
nums1 = [2,2,1,1,1,2,2]
print(majority_element(nums1))  # 输出 2

# 测试 2：不存在绝对众数
nums2 = [1,2,3,4,5]
print(majority_element(nums2))  # 输出 None

# 测试 3：简化版（假设存在）
print(majority_element_simple(nums1))  # 输出 2

五、算法扩展 求解出现次数超过 n/k 的元素

摩尔投票法可以扩展到求解 数组中出现次数超过 n/k 的所有元素，这是面试高频进阶考点，核心逻辑是「最多有 k-1 个元素满足条件」。

核心思路

1. 维护一个候选字典candidates，存储最多 k-1 个候选元素及其计数；
2. 遍历数组时：
   • 若当前元素在候选字典中，计数 +1；
   • 若候选字典的大小 < k-1，将当前元素加入字典，计数设为 1；
   • 否则，将所有候选元素的计数 -1，若计数变为 0，从字典中删除该元素；
3. 遍历结束后，验证候选字典中的元素，统计其真实出现次数，确认是否超过 n/k。

扩展版代码（求解超过 n/3 的元素）

def majority_element_k(nums, k=3):
    # 步骤 1：抵消阶段，最多 k-1 个候选
    candidates = {}
    for num in nums:
        if num in candidates:
            candidates[num] += 1
        elif len(candidates) < k - 1:
            candidates[num] = 1
        else:
            # 所有候选计数 -1，删除计数为 0 的
            to_remove = []
            for key in candidates:
                candidates[key] -= 1
                if candidates[key] == 0:
                    to_remove.append(key)
            for key in to_remove:
                del candidates[key]
    
    # 步骤 2：验证阶段
    n = len(nums)
    res = []
    for key in candidates:
        total = nums.count(key)
        if total > n // k:
            res.append(key)
    return res

# 测试：找超过 n/3 的元素
nums = [3,2,3,1,1,2,2]
print(majority_element_k(nums))  # 输出 [2,3]

六、算法复杂度分析

时间复杂度 O(n)

• 基础版：两次遍历数组，总时间复杂度为 O(n)+O(n)=O(n)；
• 扩展版：遍历数组的时间为 O(n)，验证阶段的时间为 O(k×n)，由于 k 是常数，整体仍为 O(n)。

空间复杂度 O(1)（基础版）/ O(k)（扩展版）

• 基础版：仅使用两个变量 candidate 和 count，空间复杂度为常数级；
• 扩展版：候选字典最多存储 k-1 个元素，空间复杂度为 O(k)，k 为常数时也视为常数空间。

七、关键细节 避坑指南 笔试必看

细节 1 验证阶段不能省略

这是最容易踩的坑！如果数组中不存在绝对众数，算法也会返回一个候选值，必须通过验证才能确认结果。 例如数组 [1,2,3]，算法会返回 3，但 3 的出现次数只有 1 次，不满足超过 3/2=1.5 的条件。

细节 2 算法的适用前提

摩尔投票法仅适用于求解出现次数超过 n/k 的元素，如果题目要求「出现次数最多的元素」（不要求超过 n/k），则需要用哈希表统计频次，无法使用该算法。

细节 3 扩展版的候选数量限制

求解超过 n/k 的元素时，最多有 k-1 个元素满足条件，这是数学定理。 例如 k=2 时最多 1 个，k=3 时最多 2 个，利用这个性质可以限制候选字典的大小。

细节 4 抵消阶段的顺序不影响结果

无论数组的遍历顺序如何，最终得到的候选值都是相同的（如果存在绝对众数），因为抵消的本质是「不同元素两两消除」，与顺序无关。

八、摩尔投票法 vs 哈希表法 核心对比

两者都是求解众数问题的常用方法，面试中经常作为对比考点，必须牢记区别和适用场景：

适用场景选择

1. 题目明确要求「找超过 n/2 的元素」且空间复杂度要求 O(1) → 优先用 摩尔投票法；
2. 题目要求「找出现次数最多的元素」或「统计所有元素的频次」→ 用 哈希表法；
3. 工程开发中，如果数据量不大，哈希表法更易实现和维护；如果内存受限，摩尔投票法是最优选择。

九、核心总结

1. 摩尔投票法 是求解绝对众数的最优算法，时间 O(n)、空间 O(1)，核心是「抵消思想」；
2. 基础版两步走：抵消阶段找候选 + 验证阶段确认，验证阶段不能省略；
3. 扩展版可求解超过 n/k 的元素，最多有 k-1 个候选，空间复杂度 O(k)；
4. 算法的适用前提是「元素出现次数超过 n/k」，不满足则无法使用；
5. 对比哈希表法，摩尔投票法的优势是空间效率，劣势是适用场景有限；
6. 核心原理：多数元素的出现次数超过其他元素总和，抵消后必然剩余。