摩尔投票法能O(1)空间找众数，因其仅用候选者和计数两个变量，通过抵消逻辑确保众数（出现次数＞n/2）最终胜出，但必须二次验证；不适用于非超半数场景或top-k高频统计。
摩尔投票法为什么能O(1)空间找众数
它不统计频次，也不存哈希表，只靠「抵消」逻辑：把候选者和票数当成一个寄存器，遍历中遇到相同值就+1，不同就-1；归零就换候选者。只要众数存在（出现次数 > n/2），它最终一定会留在寄存器里——因为它的票数比所有其他元素加起来还多，不可能被彻底抵消掉。
注意：该算法**只保证在众数存在时返回正确结果**；如果不确定是否存在，必须二次遍历验证 count 是否真超半数。
- 适用前提：数组非空，且明确有唯一众数（或你想检测是否存在）
- 不适用于「找出现次数 ≥ n/3 的所有元素」这类变种（需用扩展版，空间不再是 O(1)）
- 对浮点、自定义对象等可比类型也适用，但需确保
==行为合理
Python实现摩尔投票法的三步写法
别写成教科书式两遍循环嵌套，直接拆成初始化、主扫描、验证三步，清晰且不易漏验证：
candidate = None count = 0 <h1>第一遍：找候选</h1><p>for x in nums: if count == 0: candidate = x count = 1 elif x == candidate: count += 1 else: count -= 1</p><h1>第二遍：验证是否真超半数</h1><p>if nums.count(candidate) > len(nums) // 2: return candidate else: return None # 或抛异常，依需求定</p>
-
nums.count(candidate)简洁但最坏 O(n)，若已知众数必存在，可跳过这步 - 避免用
collections.Counter，它开 O(n) 空间，违背「O(1)空间」初衷 - 别用
list.index()或max(..., key=...)，它们隐含遍历或额外存储
常见报错和边界踩坑
实际调试时，多数问题出在没想清「众数定义」或忽略输入约束：
立即学习“Python免费学习笔记（深入）”；
- 输入空列表：
nums = []→ 必须提前判空，否则candidate保持None，验证时nums.count(None)报错或逻辑错 - 多个高频但都不超半数，如
[1,2,3]→ 算法仍会返回某个值（比如 3），但验证失败，所以**验证步不可省** - 用
is替代==比较候选值 → 对小整数可能碰巧对，但对大数、字符串、对象必错，坚持用== - 误以为能直接用于「找 top-k 高频」→ 摩尔法本质是「超半数探测器」，不是通用频次统计工具
和 Counter 方案对比的真实代价
有人图快直接写 Counter(nums).most_common(1)[0][0]，看起来一行，但背后是 O(n) 空间 + 哈希建表开销。在嵌入式、流式处理或内存受限场景下，这差异立刻显现：
-
Counter至少存 k 个键值对（k 是去重后元素数），最坏 O(n)；摩尔法永远只用两个变量 - 摩尔法缓存友好，纯顺序读，无随机内存访问；
Counter涉及哈希桶分配、扩容、冲突处理 - 若只是判断「是否存在众数并返回」，摩尔法两趟遍历约 2n 次比较；
Counter一趟建表 + 一趟找最大，但常数更大
真正难的是想清楚你要的到底是不是「严格意义上的众数」——很多人其实要的是「最高频元素」，那摩尔法就不适用，得换方案。
