多数元素是最朴素的数组题却藏着算法思维的分水岭哈希表 O(n) 空间人人都行但只用两个变量、单遍扫完的 1981 年投票算法才能一路推广到 n/3、n/k 和流式场景。本文讲透直觉、严格证明、三语言实现与 229 的双候选推广。引子多数元素——最朴素的问题藏着算法思维的分水岭给你一个数组找出出现次数超过一半的元素。LeetCode 169一道 Easy。大多数人第一反应是哈希表统计每个元素的次数扫完再找超过 n/2 的那个。哈希表没错O(n) 时间很漂亮。但空间是 O(n)——如果面试官紧接着说能不能 O(1) 空间很多人才意识到这道 Easy 题真正的考点是**能不能用常数空间做出来**。答案是一个 1981 年就提出的算法——摩尔投票法Boyer-Moore Majority Vote[1]。它只用两个变量单次遍历就找到多数元素。还能一路推广到超过 n/3 的元素229甚至超过 n/k天然适配数据流。一、多数元素为什么空间才是分水岭1.1 题目169. 多数元素给定大小为 n 的数组 nums返回其中的多数元素出现次数 ⌊n/2⌋。题目保证多数元素存在[2]。1.2 直觉解法哈希表统计次数O(n) 时间、O(n) 空间——正确但不优雅排序排序后取nums[n/2]O(n log n) 时间、O(1) 空间——空间达标但时间退化1.3 为什么常数空间是分水岭数据量百万级时O(n) 空间在内存上吃不消。更重要的是单遍 常数状态意味着可以流式处理——数据不用全部载入内存。这个性质把摩尔投票与只能离线的哈希/排序区分开。二、摩尔投票的直觉投票与抵消2.1 一个候选 一个计数器维护candidate当前候选和count票数遍历时执行三条规则[1][3]for x in nums: ① 若 count 0candidate xcount 1 # 没人当候选你上 ② 否则若 x candidatecount 1 # 支持者投一票 ③ 否则count - 1 # 反对者抵消一票2.2 为什么众数抵消不完把数组想象成选举candidate是当前领先者count是领先票数遇到不同元素就抵消一票。为什么多数元素一定留到最后因为多数元素出现 n/2 次其他元素加起来 n/2 次。即便所有非多数票全部用来抵消多数票也是多数票 非多数票——抵消不完剩下的净领先票必属多数元素[4]。三、正确性证明不变量是灵魂不变量任意时刻count等于候选者的票数中尚未被其他元素抵消掉的部分。归纳证明初始candidate 空、count0不变量成立①换候选count0旧候选已被完全抵消提当前元素为候选、count1即1 张未抵消票成立②支持xcandidate新来一张支持票未抵消票数 1成立③反对x≠candidate来一张反对票抵消 1 张未抵消票成立结论若多数元素 m 出现 n/2 次其票数大于其余票数之和无论反对票如何分配m 的票永远不可能被全部抵消——结束时 candidate 必为 m[4]。一句话这不是碰巧猜对而是每个元素都真实参与了投票与抵消多数者凭数量优势必然胜出。四、LeetCode 169 实战三语言实现4.1 Cclass Solution { public: int majorityElement(vectorint nums) { int candidate 0, count 0; for (int x : nums) { if (count 0) { candidate x; count 1; } else if (x candidate) count; else count--; } return candidate; } };4.2 Pythonclass Solution: def majorityElement(self, nums: List[int]) - int: candidate, count 0, 0 for x in nums: if count 0: candidate, count x, 1 elif x candidate: count 1 else: count - 1 return candidate4.3 Javaclass Solution { public int majorityElement(int[] nums) { int candidate 0, count 0; for (int x : nums) { if (count 0) { candidate x; count 1; } else if (x candidate) count; else count--; } return candidate; } }4.4 一题多解对比解法时间空间流式备注哈希表O(n)O(n)✗最直觉排序O(n log n)O(1)✗取中位随机化期望 O(n)O(1)✗抽样验证分治O(n log n)O(log n)✗左右合并位运算O(n·log M)O(1)✗逐位过半DSA-26 思路摩尔投票O(n)O(1)✓单遍、常数状态注意169保证多数元素存在第一遍投票结果无需验证[2]——这点在 229 里会反转。五、LeetCode 229 推广n/3 的双候选博弈5.1 题目与最多两个229. 众数 II返回所有出现次数 ⌊n/3⌋ 的元素。关键事实出现次数 n/3 的元素最多只有 2 个——若有 3 个3 × (n/3) n矛盾[5]。所以 229 本质用两个候选 两个计数器跑一遍投票找最多两个候选再第二遍扫描验证是否真 n/3。5.2 双候选算法流程维护 (c1,c2) 与 (cnt1,cnt2) 第一遍抵消提名 for x in nums: if x c1: cnt1 elif x c2: cnt2 elif cnt1 0: c1 x; cnt1 1 elif cnt2 0: c2 x; cnt2 1 else: cnt1--; cnt2-- # 三个阵营互相抵消 第二遍验票 统计 c1、c2 真实出现次数保留 n/3 的5.3 第二遍验证新手最容易漏的坑169题目保证存在多数元素 → 第一遍候选一定是答案229可能没有 n/3 的元素 → 第一遍候选只是提名可能名不副实例[1, 2, 3]各出现一次第一遍会提名两个候选如 2、3但没有任何元素 n/31。不二次验证就会把 2、3 都错当答案[5]。先提名、后验票——这是 229 教给我们最重要的一课。5.4 一般化到 n/k推广到k-1 个候选 k-1 个计数器可解所有出现次数 n/k 的元素[6]规律出现次数 n/k 的元素最多 k-1 个。 第一遍维护 k-1 组候选互相抵消 第二遍统计真实次数保留 n/k 的候选复杂度O(n) 时间、O(k) 空间k 通常为小常数。六、流式场景与我的观点6.1 数据流众数单遍 常数状态让摩尔投票在数据流场景大放异彩实时日志统计、在线投票、传感器数据流——数据边到边处理无需存储全部历史[6]。6.2 与 DSA-26 位运算的呼应上一期讲位运算的常数空间技巧异或去重、lowbit。摩尔投票是又一个反直觉但优雅的常数空间算法——算法思维的分水岭往往就在于敢不敢丢弃多余状态。6.3 我的三条心得心得一Easy 题的隐藏考点是空间意识。169 用哈希表 5 分钟能过但O(1) 空间的追问才是面试真正在测的——你有没有压缩状态的直觉。心得二先提名、后验票是通用心智模型。从 229 到现实中草拟方案再复核两阶段思维无处不在。心得三证明比直觉可靠。摩尔投票感觉对但写出不变量、做归纳证明才算真正掌握——这也是 DSA 系列强调的以教促学。参考资料[1] Boyer Moore 1981《MJRTY - A Fast Majority Vote Algorithm》一级[2] LeetCode 169 官方题解一级[3] doocs/leetcode 题解库Moore Voting二级[4] CodeBricks《Majority Element: Boyer-Moore Voting Algorithm》三级[5] LeetCode 229 官方题解一级[6] 力扣讨论区《摩尔投票解决所有 1/2、1/3、1/4 的众数问题》二级[7] AlgoMonster169/229 解法拆解二级