企业官网建设流程全解析

“多数元素”这道题，我刷过很多遍。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是偶数，n=2k，那么cnt > k，也就是说m的数量至少是k+1。如果m全部靠左占据0到k，此时下标k（也就是n//2）恰好是第k+1个位置——m有k+1个，所以这个位置一定是m。如果m全部靠右占据k+1到2k-1，下标k对应的是左边部分，此时最靠左的m在下标k+1？不对，这里要重新算：m占k+1个位置时，最靠左的情况下标是 n - (k+1) = 2k-k-1 = k-1？ 不对，如果占的是最后k+1个位置，就是下标k-1到2k-1，那下标k在中间，被m覆盖。如果占的是最前k+1个位置，就是下标0到k，下标k被覆盖。两种极端都覆盖了中间位置，那任意分布当然也覆盖。n是奇数时同理，n=2k+1，cnt > k+0.5，由于cnt是整数，所以cnt ≥ k+1，中间下标是k，m最靠左占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（或者说记录当前擂主被多少人支持）。

擂台赛开始时（count=0），擂台上空的，来一个元素就暂时当擂主（candidate = 当前元素）。之后每个元素上台，如果和擂主同阵营（x == candidate），支持人数+1；如果不同阵营，支持人数-1，相当于消耗掉一个支持者。一旦支持人数降到0，说明当前擂主阵营被消耗光了，擂主换成下一个上台的人。

关键点在于：多数元素m数量超过一半，这意味着即使所有非m元素都联合起来，一对一和m阵营的人抵消，m阵营依然会剩下至少一个人。所以无论抵消顺序怎么打，最后擂台上站着的人一定是m。这个结论不依赖抵消顺序，非常稳。

4.2 常见疑问：中途被换下去怎么办

我最初担心的是：擂主中途被换下去了，但台上最后那个人不是m怎么办？答案是：不可能。因为每次换擂主，一定是count减到0才换的，count=0意味着之前积累的“当前候选阵营人数优势”被完全抵消掉了。把整个数组看成一连串抵消过程，m是唯一总数量占优的阵营，在任何一段前缀里，m的优势可以被暂时追平，但全部遍历完，优势一定回到m这边。

为了验证这个直觉，我做过一个非常“恶心”的测试用例：数组是[1, 2, 1, 3, 1, 2, 1]，多数元素是1，出现4次超过7的一半（3.5）。手动跑一遍摩尔投票：开始candidate=None, count=0；元素1上台，candidate=1, count=1；元素2上台，不同阵营，count=0；此时擂台空了；元素1上台，candidate=1, count=1；元素3上台，count=0；元素1上台，candidate=1, count=1；元素2上台，count=0；最后一个元素1上台，candidate=1, count=1。最后输出1，正确。中间擂主被换了两次，但最终仍然是1，因为它总数压过所有对手的总和。

再举一个更刁钻的例子：[2, 2, 1, 1, 1, 2, 2]，多数元素2出现4次。跑一遍：2上台count=1；2上台count=2；1上台count=1；1上台count=0，换擂主，当前候选变为1，count=1（这是1阵营第一次短暂占优）；下一个元素1上台，1同阵营，count=2；元素2上台，抵消为1；元素2上台，抵消为0，换擂主为2，count=1。最后输出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 -1

5. 从多数到众数：分治、随机化与位运算的奇思妙想

除了上面三种主流思路，这道题还有几种更“偏门”但特别能体现思维广度的解法。我把它们放在一起讲，是因为它们背后分别代表了三种完全不同的算法思想——分治、随机化、位运算。面试时你未必需要写出它们，但了解它们能让你对这道题的理解更深一层。

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 举一反三：多数元素题目家族

这道题延伸出去，有三个变体非常值得刷，我列成表格方便对照。

229题的思路我提一句：出现次数超过n/3的元素最多只能有2个，所以可以维护两组候选和计数器，遍历一次后，再统计两个候选的真实出现次数，过滤掉不达标的。理解169的摩尔投票后，229就是套一套模板的事，但需要自己动手推一遍才能记住细节。

6.3 工程视角的一个另类应用

除了刷题，多数元素这个概念在工程里也有实用场景。比如日志分析中，如果某条错误信息出现的次数超过了总日志量的一半，那它大概率是当前系统故障的主要矛盾，没必要把所有错误都列出来逐个排查。这时候你可以把海量日志流看作数组，用一个内存占用极小的摩尔投票算法在线扫描，实时返回当前最“主流”的错误类型，而不需要把全部日志存储在内存里再统计。这类“数据流中的多数元素”问题，O(1)空间这个特性非常宝贵，因为流式数据根本没法全部缓存。

我在公司处理线上日志时，曾经用类似思路写过一个小工具，每来一条日志就更新一次候选和计数，几分钟内就能定位到压倒性多数的异常类型，比先落库再跑SQL统计快得多。这算是这道“简单题”在现实世界里的一个意外延伸吧。

最后再分享一个刷题习惯上的建议：像169这种解法很多的题目，千万别只记住最优解就收工。我刷题这几年，最大的体会是，一道题能带来多少成长，不取决于你解出来的那一刻有多快，而取决于你愿不愿意把它的所有解法都过一遍，想想每种解法的“为什么”。哈希解法为什么空间高？排序法为什么能靠中位数？摩尔投票为什么空间O(1)还能保证正确？分治和随机化又分别牺牲了什么换取了什么？这些东西想明白了，你遇到变体题时就不会慌，因为你掌握的不是一段代码，而是一套选择的逻辑。