“多数元素”这道题我刷过很多遍。LeetCode热题100里它被标成“简单”但说实话我第一次看到这题时脑子里迅速闪过的暴力解法连O(n)的时间复杂度都达不到。后来陆陆续续见过它出现在不少公司的笔试题里也看过身边同事用各种奇奇怪怪的方法去解我才意识到一道题被标记为“简单”往往不是因为思路只有一个而是因为它藏着一整个解法谱系从最暴力的哈希计数到最优雅的摩尔投票中间隔着好几层思维阶梯。这篇文章就想把这条阶梯完整铺开来聊聊169.多数元素这道题背后值得咀嚼的东西包括每种解法的原理、证明、边界条件和面试场合下怎么选型最稳。无论你是刚准备刷题的新手还是想在面试里把“简单题”答出区分度的老手这篇应该都能给你点实际帮助。1. 多数元素的数学本质超过一半意味着什么先回到题目本身。给定一个大小为n的数组nums要求返回其中的多数元素。所谓多数元素是指在数组中出现次数大于 n/2 的元素向下取整的意义上严格超过一半。题目默认这个元素一定存在不需要你处理不存在多数元素的情况。这个“一定存在”的保证看起来只是简化了边界判断但恰恰是它让很多巧妙解法有了立足的土壤。我在给朋友讲这道题的时候喜欢先用一个极端例子建立起直觉假如一个班有51个人投票选班长超过一半的人选了小明那小明一定是班长。这个“超过一半”不是一个随意定的线它意味着两件事。第一多数元素和其他所有元素的数量之和比起来一定是净胜的——哪怕其他每个元素都联合起来反对它它的数量也压过所有人。第二这个属性在局部区间里是有传递性的把一个数组劈成两半多数元素至少在其中一半里仍然能构成多数这一点后面分治解法会用到先记住这个直觉。从数学表达上看设众数多数元素为m出现次数为count(m) n/2那么其余所有元素的数量 n - count(m) n/2。这个不等式看似平平无奇但它是摩尔投票解法所有抵消逻辑的根源。你可以把“数量大于一半”想象成一场拔河众数队伍比对面所有队伍加起来还多至少一个人那么无论对面怎么组队只要一对一抵消最后场上站着的必然是众数那一边的人。这个数学本质还能解释一个问题为什么不能直接排序后取中间值就草草了事——当然可以但排序本身有O(n log n)的开销而“超过一半”这个条件蕴含的信息量其实比排序要强得多。我们做算法题时经常有一个误区看到数组就先想排序但排序会给所有元素安排位置而这道题只关心“谁占了一半以上”排序的全局有序性其实是过度的信息。后文的所有线性解法本质上都是围绕“半数”这个阈值做文章而不是围绕“有序”。2. 暴力与哈希计数拿到题最容易想到的两条路先别急着上最优解。任何算法题我习惯从最笨的办法开始推因为笨办法能帮你确认对题目的理解是不是正确的。2.1 双层循环暴力统计最朴素的做法就是两层循环外层枚举每一个候选元素内层遍历数组统计它出现的次数一旦发现某个元素出现次数超过n/2立刻返回。def majorityElement(nums): n len(nums) for i in range(n): cnt 0 for j in range(n): if nums[j] nums[i]: cnt 1 if cnt n // 2: return nums[i] return -1这段代码的优点是逻辑零门槛你甚至不需要知道“超过一半”到底有多重要只需要会写循环就能写完。缺点是时间复杂度O(n^2)在LeetCode的测试数据下n可以到5*10^4甚至更大这个复杂度基本会超时。但它依然有价值第一它是验证你对题目理解是否正确的最快方式第二当你拿到一道新题完全没思路时先写出暴力解让程序跑通再去优化这是很多竞赛选手的习惯因为“能跑的暴力算法”比“纸上谈兵的最优解法”更接近正确答案。2.2 哈希表计数时间换空间的经典操作暴力解法慢在每次统计都要重新遍历整个数组。那我们自然想到能不能只遍历一遍把所有元素的出现次数都记下来答案就是哈希表。用一个字典key存元素value存出现次数一趟扫完再扫一遍哈希表找出value最大的key或者边统计边判断是否已经超过n/2。def majorityElement(nums): cnt {} for x in nums: cnt[x] cnt.get(x, 0) 1 if cnt[x] len(nums) // 2: return x return -1这里有一个细节值得说我是在循环内部直接判断cnt[x]是否从严超过n/2。因为题目保证一定存在多数元素所以一旦某个元素的计数达到阈值就可以提前返回不需要等整个循环结束。这个“提前返回”的习惯在哈希表类题目里很常用能省一点运行时间虽然复杂度不变但跑出来的实际耗时会好看一些。哈希解法的时间复杂度是O(n)空间复杂度是O(n)。它空间换时间的思路非常通用但放在这道题里有个尴尬之处——题目如果用“常数空间”作为隐性要求哈希表就会被卡掉。LeetCode上的题目描述里通常不会强制要求O(1)空间但面试官一定会追问你能不能做到O(1)空间所以哈希表解法通常是“二十分钟内能接受的解法”而不是“让面试官眼里放光的解法”。3. 排序法里的隐藏证明为什么中位数一定是对的哈希之后很多人会想到排序。把数组排好序多数元素出现次数超过一半那么排完序后数组正中间那个位置下标n//2的元素必然就是多数元素。这个结论好记但许多人只知道用不知道证明面试被一问就容易卡壳。我把这个证明拆开讲。设数组长度为n排序后下标从0到n-1。多数元素m出现次数cnt n/2。现在考虑它可能出现在哪些下标区间。最极端的两种情况是m全部集中在最前面占据0到cnt-1或者全部集中在最后面占据n-cnt到n-1。只要证明无论m怎么分布下标n//2这个位置一定能被m覆盖结论就成立。分情况来看。如果n是偶数n2k那么cnt k也就是说m的数量至少是k1。如果m全部靠左占据0到k此时下标k也就是n//2恰好是第k1个位置——m有k1个所以这个位置一定是m。如果m全部靠右占据k1到2k-1下标k对应的是左边部分此时最靠左的m在下标k1不对这里要重新算m占k1个位置时最靠左的情况下标是 n - (k1) 2k-k-1 k-1 不对如果占的是最后k1个位置就是下标k-1到2k-1那下标k在中间被m覆盖。如果占的是最前k1个位置就是下标0到k下标k被覆盖。两种极端都覆盖了中间位置那任意分布当然也覆盖。n是奇数时同理n2k1cnt k0.5由于cnt是整数所以cnt ≥ k1中间下标是km最靠左占0到k最靠右占k到2k下标k都落在覆盖区间内。上面这段推导看起来有点绕但核心就一句话因为多数元素数量过半无论它怎么挤数组一半位置正中间这个点都会被它“压住”。这个性质是排序解法能成立的根基。代码实现更简单def majorityElement(nums): nums.sort() return nums[len(nums) // 2]复杂度是O(n log n)如果语言内置排序Python的Timsort效率很高实际跑起来往往不慢。但我觉得这个解法在面试里适合做“过渡方案”而不是“最终解”因为排序引入了全局有序这个多余信息面试官会期待你进一步优化到O(n)时间、O(1)空间。4. 摩尔投票一次遍历找到多数的精妙设计终于聊到这道题最出名的解法——Boyer-Moore多数投票算法Moore Voting Algorithm。我第一次看这个算法的代码时愣了几秒因为这段代码短到让人怀疑是不是有bug。def majorityElement(nums): candidate None count 0 for x in nums: if count 0: candidate x count 1 if x candidate else -1 return candidate就这么几行遍历一次空间O(1)最后candidate就是多数元素。我第一次跑通之后心里是有个疑问的凭什么这个candidate一定是多数元素中间那个count到底是什么含义为了彻底弄懂它我试了好几种理解方式最后发现“配对抗衡”的比喻最直观。4.1 把数组想象成一场擂台赛假设数组里每个元素都是一个人他们要打擂台。多数元素这方人多势众所有其他元素是散兵游勇。擂台规则是两个人一旦相遇就一起下场抵消不同阵营的人相遇双方各消耗一个同阵营的人相遇己方力量1或者说记录当前擂主被多少人支持。擂台赛开始时count0擂台上空的来一个元素就暂时当擂主candidate 当前元素。之后每个元素上台如果和擂主同阵营x candidate支持人数1如果不同阵营支持人数-1相当于消耗掉一个支持者。一旦支持人数降到0说明当前擂主阵营被消耗光了擂主换成下一个上台的人。关键点在于多数元素m数量超过一半这意味着即使所有非m元素都联合起来一对一和m阵营的人抵消m阵营依然会剩下至少一个人。所以无论抵消顺序怎么打最后擂台上站着的人一定是m。这个结论不依赖抵消顺序非常稳。4.2 常见疑问中途被换下去怎么办我最初担心的是擂主中途被换下去了但台上最后那个人不是m怎么办答案是不可能。因为每次换擂主一定是count减到0才换的count0意味着之前积累的“当前候选阵营人数优势”被完全抵消掉了。把整个数组看成一连串抵消过程m是唯一总数量占优的阵营在任何一段前缀里m的优势可以被暂时追平但全部遍历完优势一定回到m这边。为了验证这个直觉我做过一个非常“恶心”的测试用例数组是[1, 2, 1, 3, 1, 2, 1]多数元素是1出现4次超过7的一半3.5。手动跑一遍摩尔投票开始candidateNone, count0元素1上台candidate1, count1元素2上台不同阵营count0此时擂台空了元素1上台candidate1, count1元素3上台count0元素1上台candidate1, count1元素2上台count0最后一个元素1上台candidate1, count1。最后输出1正确。中间擂主被换了两次但最终仍然是1因为它总数压过所有对手的总和。再举一个更刁钻的例子[2, 2, 1, 1, 1, 2, 2]多数元素2出现4次。跑一遍2上台count12上台count21上台count11上台count0换擂主当前候选变为1count1这是1阵营第一次短暂占优下一个元素1上台1同阵营count2元素2上台抵消为1元素2上台抵消为0换擂主为2count1。最后输出2。即使1阵营一度占优最终还是被2翻盘因为2的总数超过一半。4.3 摩尔投票的时间与空间时间复杂度O(n)空间复杂度O(1)。这是理论上最优雅的解。它之所以能成立靠的正是题目中“多数元素数量超过一半”这个强约束。去掉这个约束算法就不能直接用了。LeetCode原题里虽然多数元素必然存在但如果你要处理“不存在多数元素”的情况需要在摩尔投票结束后再遍历一次数组数一数candidate到底出现了几次确认它真的超过一半否则就返回-1或者None。我建议把这一步作为习惯写进代码里因为很多面试题的变体恰恰会取消“必存在”这个前提。def majorityElement(nums): candidate None count 0 for x in nums: if count 0: candidate x count 1 if x candidate else -1 # 验证阶段确保 candidate 确实是多数元素 if nums.count(candidate) len(nums) // 2: return candidate return -15. 从多数到众数分治、随机化与位运算的奇思妙想除了上面三种主流思路这道题还有几种更“偏门”但特别能体现思维广度的解法。我把它们放在一起讲是因为它们背后分别代表了三种完全不同的算法思想——分治、随机化、位运算。面试时你未必需要写出它们但了解它们能让你对这道题的理解更深一层。5.1 分治法把大问题切成小问题将数组从中间一分为二分别求出左半部分的多数元素和右半部分的多数元素。如果左右两半的多数元素相同那整个数组的多数元素就是这个元素。如果不同就分别统计这两个元素在整个数组里出现的次数取出现次数更多的那个。这个解法的正确性依赖一个关键性质我在文章开头埋过伏笔如果元素m是整个数组的多数元素那么m至少是左半数组或右半数组之一的多数元素。这很重要因为如果m在左右两半里都不超过一半那它在整个数组里也不可能超过一半左右两半加起来m的总占比是两个不超过一半的加权平均不可能过半。所以递归求解左右两半的候选再合并是安全的。递归出口是数组只有一个元素时这个元素就是该子数组的多数元素。合并时统计两个候选的全局出现次数。整体时间复杂度O(n log n)空间复杂度O(log n)递归栈代码实现def majorityElement(nums): def helper(l, r): if l r: return nums[l] mid (l r) // 2 left_major helper(l, mid) right_major helper(mid 1, r) if left_major right_major: return left_major left_cnt sum(1 for i in range(l, r 1) if nums[i] left_major) right_cnt sum(1 for i in range(l, r 1) if nums[i] right_major) return left_major if left_cnt right_cnt else right_major return helper(0, len(nums) - 1)分治法在理解上比摩尔投票更“正统”一些很多算法教材里都把它作为分治思想的例题。它的缺点是常数比较大实际运行效率不如摩尔投票但胜在思路通用——如果题目改成“求出现次数超过n/3的元素”LeetCode 229题分治思想依然有变形的空间。5.2 随机化概率论给的惊喜解法随机化解法非常取巧每次随机选一个下标判断这个元素是不是多数元素。因为多数元素出现概率大于1/2所以随机选一次选中的概率超过50%重复多次比如20次失败概率降到极低。从概率上讲用20次随机采样验证失败率不到百万分之一对于实际工程和算法竞赛都足够了。import random def majorityElement(nums): n len(nums) while True: candidate random.choice(nums) if sum(1 for x in nums if x candidate) n // 2: return candidate这个解法的“理论最坏复杂度”是无穷大因为运气差可能一直选不中但期望复杂度是O(n)每轮随机选和统计都是O(n)期望轮数是常数。我平时在非正式场合提到这个解法主要是为了说明一个观点算法不一定要“每次都对”如果概率上几乎对很多场景下也够用。不过面试时写随机化解法有一定风险因为面试官如果对概率论不熟可能会觉得你在抖机灵。我建议把它作为“脑洞拓展”在聊天中提到而不是当作最终代码提交。5.3 位运算从二进制视角硬算用一种更“底层”的角度看多数元素在每一个二进制位上的值一定等于所有元素在该位上出现次数更多的那个值。因为如果多数元素在某一位是1那么这一位上1出现的次数一定超过一半。把每个位独立统计最后拼接出整个数字。def majorityElement(nums): n len(nums) ans 0 for bit in range(32): cnt 0 for x in nums: if (x bit) 1: cnt 1 if cnt n // 2: ans | (1 bit) # 处理 Python 整数符号问题如果超过 2^31-1 需要转负数 return ans if ans 2**31 else ans - 2**32这里有个Python处理细节Python的整数是任意精度而LeetCode的测试用例里多数元素通常是32位有符号整数范围内的值。如果第31位从0开始编号是1说明这个数可能是负数。所以我在返回之前做了判断把大于等于2**31的二进制模式转换成负数表示。这个细节不处理的话某些负数用例会直接算错我当初就在这上面栽过一次。位运算的时间复杂度是O(32n) O(n)空间O(1)常数比摩尔投票大但它体现的“逐位独立统计”思想在别的一些题目比如求数组中出现奇数次的数里很有用。6. 面试实战与题目家族这道“简单题”怎么答出区分度聊完算法本身再说说更实际的层面面试时遇到这道题怎么表现才能让面试官觉得你不只是背过答案。我在模拟面试里见过不少候选人上来就默写摩尔投票但被追问“为什么这样写是正确的”时就卡住了。这道题真正的考察点其实在于你是否理解算法的成立条件。6.1 回答路径建议如果你是面试者我建议按这个顺序展开回答第一步先复述题目确认“多数元素必然存在”。这一步不是废话它表明你在界定问题的边界。如果题目说“可能不存在”你的解法就要加验证步骤。第二步从暴力或哈希开始快速给出一个能跑的正确解法。这让面试官觉得你的基础是扎实的。哈希版本边统计边判断展示你注意了提前返回的优化。第三步在面试官追问“能不能优化空间”时引出排序法顺势指出O(n log n)还不够优然后过渡到摩尔投票。第四步写摩尔投票时不要只写代码先用一句话解释核心思想“异阵营两两抵消因为多数元素数量过半所以最后剩下的候选一定是它。”然后一边写代码一边把维护candidate和count的过程讲清楚。第五步展示代码后主动说“如果题目可能不存在多数元素我会再遍历一次验证候选元素出现次数是否真的超过一半。”这句话很容易让面试官眼前一亮因为大多数人会无视验证这一步。6.2 举一反三多数元素题目家族这道题延伸出去有三个变体非常值得刷我列成表格方便对照。题目要求核心思路LeetCode 169 多数元素出现次数 n/2必存在摩尔投票LeetCode 229 求众数 II出现次数 n/3 的所有元素最多2个扩展版摩尔投票维护两个候选LeetCode 1150 检查多数元素是否存在判断目标值是否出现超过一半二分查找目标值首次出现位置和最后一次出现位置229题的思路我提一句出现次数超过n/3的元素最多只能有2个所以可以维护两组候选和计数器遍历一次后再统计两个候选的真实出现次数过滤掉不达标的。理解169的摩尔投票后229就是套一套模板的事但需要自己动手推一遍才能记住细节。6.3 工程视角的一个另类应用除了刷题多数元素这个概念在工程里也有实用场景。比如日志分析中如果某条错误信息出现的次数超过了总日志量的一半那它大概率是当前系统故障的主要矛盾没必要把所有错误都列出来逐个排查。这时候你可以把海量日志流看作数组用一个内存占用极小的摩尔投票算法在线扫描实时返回当前最“主流”的错误类型而不需要把全部日志存储在内存里再统计。这类“数据流中的多数元素”问题O(1)空间这个特性非常宝贵因为流式数据根本没法全部缓存。我在公司处理线上日志时曾经用类似思路写过一个小工具每来一条日志就更新一次候选和计数几分钟内就能定位到压倒性多数的异常类型比先落库再跑SQL统计快得多。这算是这道“简单题”在现实世界里的一个意外延伸吧。最后再分享一个刷题习惯上的建议像169这种解法很多的题目千万别只记住最优解就收工。我刷题这几年最大的体会是一道题能带来多少成长不取决于你解出来的那一刻有多快而取决于你愿不愿意把它的所有解法都过一遍想想每种解法的“为什么”。哈希解法为什么空间高排序法为什么能靠中位数摩尔投票为什么空间O(1)还能保证正确分治和随机化又分别牺牲了什么换取了什么这些东西想明白了你遇到变体题时就不会慌因为你掌握的不是一段代码而是一套选择的逻辑。