在力扣LeetCode上刷题的人大概率都绕不过这两道题136. 只出现一次的数字Single Number和169. 多数元素Majority Element。它们都属于“热题100”级别的高频面试题而且看起来毫不相关——一个找出只出现一次的数字一个找出出现次数过半的数字。但如果你把这两道题放在一起去刷会发现它们在思路层面非常互补一个教你用异或运算做“抵消”一个教你用投票思想做“抵消”两题各有一招官方解法之外的“神操作”。这篇文章我掰开揉碎讲清楚从暴力解法一路推到最优解再把复杂度、正确性、变体题、面试坑点全部串起来保证你看完能直接给别人讲明白。先说明一下这两道题的适用范围136题的进阶要求是“不使用额外空间”169题的官方要求是“尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法”。也就是说面试官几乎一定会追问最优解。所以这篇文章适合正在刷题准备面试的选手也适合想补位运算和计数思想短板的同学。我会把两道题的核心解法和背后的推导过程全部拆开配合具体例子让你不止记住代码而是真正理解“为什么这样能行”。1. 为什么把136和169放在一起讲两道题共用一套“统计”底色1.1 一道找“落单”一道找“过半”本质都是计数问题136题给你一个数组所有元素都出现两次只有一个元素出现一次让你找出来。169题给你一个数组保证有一个元素出现次数大于 n/2让你把它找出来。一个是“找唯一不成对”一个是“找次数过半”表面上一个考位运算一个考投票但它们背后其实共享同一条底层逻辑在一个集合里通过某种规则让“数量关系”显形。136题的经典场景是一堆商品里只有一个次品其他商品都恰好有一模一样的正品配对你要用最低成本把那件次品挑出来。169题的经典场景是一个投票箱里只有一张“多数票”能保证超过半数你要找到它。两个问题都没有让你排序也没有给你额外容器要求在线性时间内完成——这意味着你不能靠“数一下再比较”的朴素方法必须借助特殊的数学性质。把这两题放一起最值得咀嚼的地方在于136的最优解是异或XOR169的最优解是Boyer-Moore投票摩尔投票。它们本质上都是“抵消”的思维。异或是同一数字与自己抵消为0摩尔投票是候选人的票数被“反对票”抵消。学会这两种抵消模型之后你会发现它们能延伸拓展出一大批题目比如137. 只出现一次的数字II、260. 只出现一次的数字III、229. 求众数II等等。所以把这俩一起刷性价比极高。1.2 四类解法路线提前理清思路我以前刚开始刷题的时候遇到这种数组统计问题第一反应往往是开一个哈希表然后把元素一个个塞进去最后遍历哈希表找答案。这当然能做而且136和169都能用哈希表直接解。但哈希表的空间复杂度是 O(n)136的进阶要求不允许169的进阶要求也不允许。这就倒逼你去想优化方案。我把两道题的常见解法路线画成一张对照表你一眼就能看清各自的定位问题暴力解法通用解法进阶解法最优复杂度136 只出现一次双重循环计数哈希表统计异或运算时间 O(n)空间 O(1)169 多数元素双重循环计数哈希表统计 / 排序取中间摩尔投票 / 分治时间 O(n)空间 O(1)注意看136用哈希表能解169用哈希表也能解但两道题的最优解都不依赖额外容器。这就是面试里最常见的追问路径你能用哈希表通过只能算“及格”你能用位运算或投票搞出来才算“亮点”。下面我把两条最优解的推导过程展开来讲。2. 136. 只出现一次的数字从暴力到异或的思维跃迁2.1 暴力与哈希表正确但不讨巧的起点先看看最朴素的做法。数组长度 n你想知道哪个元素只出现一次最简单的办法是挨个检查对每个元素再扫一遍数组统计它出现几次如果发现次数是1就返回它。这个双重循环的时间复杂度是 O(n²)n一旦上万就明显吃力提交上去大概率超时。所以暴力解法只适合帮助你把问题“读明白”不适合作为最终方案。稍微进步一点用哈希表。遍历一次数组把每个元素作为key出现次数作为value存下来再遍历一次哈希表找到那个value为1的key。两次遍历时间 O(n)空间 O(n)。代码很短思路也几乎不会错我在刚刷这道题时也是这么写的。但它没有利用题目给的强约束——“其他元素均出现两次”。当你把所有元素都无差别塞进哈希表的时候其实把这个约束浪费掉了。真正的巧解得回到这个特殊的“成双成对”前提上想办法。有的同学可能还会想到排序把数组排序后相同的元素会靠在一起然后两两比较即可。这种方法时间 O(n log n)空间 O(1)如果在原数组上排。但题目要求线性时间排序法在面试里也很难拿满分。真正的最优解藏在位运算里。2.2 异或运算揭开“最优解”的面纱异或XOR满足三条核心性质这三条性质单独拿出来都平平无奇组合起来却正好解决136题归零律x ^ x 0任何数和自己异或结果变成0。恒等律x ^ 0 x任何数和0异或结果还是它自己。交换律与结合律异或运算顺序可以随意调换和加法一样。这三条性质合在一起就能玩出“抵消”的效果。走一遍逻辑假设数组是 [a, b, a, c, b]你先把所有元素全部异或起来得到 a ^ b ^ a ^ c ^ b。根据交换率把相同的项放一起变成 (a ^ a) ^ (b ^ b) ^ c再结合归零律变成 0 ^ 0 ^ c最后用恒等律得到 c。这个 c 就是只出现一次的那个数字。我上学那会儿头一次看到这个解法觉得像魔术。后来想明白了一个生活化类比就像开灯关灯。每个元素代表一次开关操作相同数字操作两次等于“灯恢复原状”只有一个数字只操作了一次所以最后灯的状态就是那个数字的“痕迹”。异或运算在硬件上非常高效这就是为什么136题的进阶要求用一行代码就能满足时间 O(n)、空间 O(1)完美命中所有约束。2.3 异或解法完整推导、代码与边界验证写代码之前先把流程固定下来初始化一个变量 result 0。遍历数组中每个元素 num执行 result result ^ num。遍历结束后返回 result。翻译成Python代码长这样def singleNumber(nums): result 0 for num in nums: result ^ num return result如果你在LeetCode上提交这个解法通常能跑进最佳区间代码量还极短。我见过不少新手在这里犯两个小错。第一个是习惯把result初始化成数组第一个元素然后从第二个元素开始异或——这样结果一样但如果数组为空就会出问题。虽然题目说“非空数组”但写代码时保持result0的写法更严谨也更好理解。第二个错误是容易把异或符号和幂运算混淆。Python里异或是^不是**C/Java里也是^不是xorC确实有关键字xor但不如符号通用。对于边界情况数组只有一个元素的情况result自始至终等于那个元素正确数组长度为奇数所有成对元素抵消只剩落单元素正确元素为负数也没问题异或是按二进制位运算负数的补码表示同样适用。这一步是纯位运算不需要额外空间时空复杂度都是 O(n) 和 O(1)。这道题做到这一步已经到头了。3. 169. 多数元素多数决背后的摩尔投票法3.1 前三种常规思路的时间成本分析169的题意很直白返回出现次数大于 n/2 的元素。最直觉的做法还是哈希表统计完再扫一遍找最大次数时间 O(n)、空间 O(n)——能过但不够“高级”。排序法在这个题上有一个非常妙的性质因为多数元素出现次数超过一半排序后数组正中间的那个位置下标 n//2一定是多数元素。所以排序后直接返回 nums[n//2] 就完事代码极其简短但代价是时间 O(n log n)空间取决于排序算法是否原地。还有一个思路是随机化随机选一个下标验证它是否为多数元素。因为多数元素占比超过1/2随机一次命中的概率就超过1/2期望上试两三次就出来了。这个解法面试里偶尔有人提属于“非典型”路线面试官不一定期待但如果你能说清概率期望和验证逻辑也能成为一个加分项。不过它最坏情况可能无限试探不算稳定解法。真正让169题成为经典的原因是接下来这个空间O(1)、时间O(n)的解法。3.2 摩尔投票法的核心思想与代码实现Boyer-Moore投票算法摩尔投票法可以这么直观理解把数组想象成一场投票每个元素是一位候选人的票。我们维护一个“候选席位”和一个“票数差额”。一开始席位为空差额为0。遍历到每个元素时如果差额等于0当前元素顶替成为新候选人差额设为1。如果当前元素等于候选人差额加1。如果当前元素不等于候选人差额减1相当于这个人的“反对票”抵消了候选人一票。因为多数元素超过半数它总能比其他所有“反对票”的总数多所以到最后留在席位上的候选人一定就是多数元素。这个过程本质上是“你方唱罢我登场”候选人会随着票数差额归零而换人但只要存在一个超过半数的真正多数它就不会被彻底抵消掉。反过来理解如果某个候选人最后还站着那它必然是在相消过程中存活下来的“最终赢家”。Python代码def majorityElement(nums): candidate None count 0 for num in nums: if count 0: candidate num count 1 elif num candidate: count 1 else: count - 1 return candidate这个代码有一个隐含前提题目保证多数元素一定存在。如果存在不保证的情况比如数组 [1, 2, 3]跑完这个算法返回的是3但3并不是多数元素出现次数没超过 n/2。所以实际面试中如果题目没有“一定存在多数元素”这个保证你需要在投票结束后再加一次扫描验证数一遍 candidate 的真实出现次数确认超过 n/2 再返回。3.3 为什么摩尔投票法一定正确正确性证明通俗版别看摩尔投票代码短很多人“会用但说不清”。面试官如果追问“为什么最后 candidate 一定是正确答案”你得能顶上。我用一个通俗论证来解释。设多数元素为 M它在数组中出现了 k 次满足 k n/2。其余所有非多数元素加起来的总数是 n - k这个数严格小于 k。摩尔投票的核心操作可以理解成每次遇到和候选人不同的元素就消耗掉“候选人一票”和“反对一票”相当于成对删除两个不同的元素。对数对删除不会改变“M超过一半”这个事实——因为在任何时刻你删掉的两张票里若有一张是M另一张必然不是M若两张都不是MM的比例只会相对变高。所以无论删除顺序如何M始终保有相对多数的地位最终不可能被完全抵消干净。换一种更贴近操作的表述每次count降到0意味着从全局视角看之前扫描区间内所有元素被“成对抵消”了。你完全可以把这个区间扔掉从下一个元素重新开始。因为M在全局占了超过一半它在任何被丢弃区间里最多只是“和对手打平”绝不会“亏损”。所以在最后剩下的区间里M必然占据多数席位。这就是为什么最终candidate不想让位也不可能——它背后站着超过半数的真实票数。4. 两题的变体与面试延伸一题多解不如一题多用4.1 136的经典变体出现两次之外的世界136题解决的是“其他元素恰好出现两次”如果把“两次”改成“三次”就是137. 只出现一次的数字II。这个变体的标准解法就不能再用简单异或了而是要用按位统计对每一位统计所有数字在该位上出现1的次数把次数对3取余剩下的位信息拼起来就是答案。思路是把二进制位上的“计数”和“取模”结合这和136的“两两抵消”异或模型形成对照异或本身等价于“按位对2取余”所以137还需要自己在更高维度上实现按位统计。再变一下如果数组里有两个元素各出现一次其他都出现两次就是260. 只出现一次的数字III。它的经典解法是先整体异或一遍得到这两个目标数字的异或结果 diff然后取 diff 中任意一个为1的二进制位把原数组分成两组——这一位是0的一组、这一位是1的一组——这样两个目标数字就必然被分到不同组同时每一组成对出现的元素仍然成对。再分别在两组内异或就能找到两个答案。这两道变体题都能直接用136的思路做基础一道题带动三道题这就是刷透经典题最实在的收益。4.2 169的经典变体从过半到超过三分之一169的“超过一半”如果改成“超过三分之一”就变成229. 求众数II要求返回所有出现次数大于 n/3 的元素。这时聪明的读者应该能意识到大于 n/3 的元素最多只能有两个所以摩尔投票法可以扩展成同时维护两个候选人和两套票数。流程上依然是“遇到候选人就加分遇到非候选人就两套票数同时减一票数归零的候选人换人”。最后再做一遍验证扫描确保返回的元素真实超过 n/3。这道题特别能考出你对摩尔投票是否“真懂”。因为候选人从1个变成2个抵消逻辑变成了三种不同元素“三方各减一票”很多背模板的人到这里就写不明白。我自己当年就是先被229卡住才回头彻底啃了169的证明。所以我的建议是别满足于能默写169的代码把“为什么成立”用自己话讲过一遍再去做229顺畅得多。4.3 这些题在真实面试与工程中的价值很多人会问我以后写业务代码哪会去异或或者投票实际上这类题的工程价值更多在于思维模型而不在于“直接照抄”。异或的“成对抵消”在数据校验里非常常见比如你有一组成对出现的日志ID想快速找出唯一的异常ID或者做奇偶校验位运算都很顺手。摩尔投票的“流式候选”思想则适用于内存受限场景你只有很小的固定内存却需要在一个很大的数据流里找可能过半的元素——这时候开哈希表根本扛不住摩尔投票只用一个变量就能一直算。从面试角度看这两道题特别适合考查“沟通能力”。因为代码短面试官想看你是不是能讲清楚复杂度、正确性、边界条件。哪怕你直接给出最优解也要能把推导过程完整说明白。现实中真有候选人背出摩尔投票代码但被问“如果没有多数元素怎么办”时卡住这就很减分。所以下面我专门把常见的坑整理成一个速查表。5. 我的刷题复盘与踩坑实录5.1 常见错误和初学者误区速查下面这张表是我自己刷题加看评论区总结出来的高频错误每一行都对应过真实案例。误区具体表现正确做法忘记读题约束136题用排序交上去TLE注意“线性时间不使用额外空间”异或初始化错误result从nums[0]开始空数组崩溃统一从0开始遍历全部元素摩尔投票不验证在“不保证存在多数”时直接返回candidate加上第二遍扫描确认出现次数位运算和逻辑运算混淆把^写成或异或^是按位是按位与逻辑与是and忽略负数/大整数用十进制手推异或结果推导失败按补码的二进制位思考结果依然正确一题背代码不做变体137、229题换皮就懵掌握模型本质尝试自己推变体这里有一个非常典型的“看着对其实不对”的例子有的同学实现摩尔投票时把elif num candidate写成if num candidate而前面又用了if count 0加上return或者continue来兜底逻辑虽然能跑通但换到229双候选人的场景就一错到底。所以写这类算法题建议先把伪代码在纸上走一遍再落到语言。5.2 刷题策略建议怎么复盘才有效我个人的经验是像136和169这类“只有几行代码”的题最容易踩的坑是“看懂了但不会自己推”。你以为自己理解了过了两天再写连异或三条性质都可能记混。复盘的时候建议按这三步走第一步不看题解自己从暴力解法开始一步步推到最优解强行解释每一步“为什么能行”。比如136题你要能说清楚“异或就是按位对2取模”169题你要能说清楚“成对消除不会改变多数元素的相对多数地位”。第二步改题目条件做变体扩展。把136的“两次”改成“三次”动手写137把169的“超过一半”改成“超过三分之一”动手写229。写不出来没关系这个卡顿过程才是真正的学习。等你回头再看原题会发现原本模糊的模型一下子清晰了。第三步反复口头讲解。找一个朋友或者对着镜子用两分钟把最优解讲明白。如果讲解过程中出现“这里就是……反正就是……”这类含糊表述说明还没完全吃透。左右互搏式的复述是检验掌握程度的蛮好用的方法。5.3 一点思考题把两题的思维模型打通试试最后留一个开放问题供有基础的朋友自己玩。数组里有一个元素出现次数超过一半同时还有一个元素只出现一次其他元素都成对出现请问能否在线性时间内同时找出这两个目标元素有人说这可以结合136的异或技巧和169的摩尔投票分开做但如何在一遍遍历内完成方法其实不止一种。我见过有人用“先摩尔投票找到多数元素再异或全数组时去掉多数元素的贡献”来解决也见过有人用更取巧的按位筛选法。这个思考题没有标准答案重点在于尝试用两题的思维模型互相配合。如果你能给出一个时间O(n)、空间O(1)的方案说明这两道题在你这里已经不仅靠背代码而是真正建立起了位运算与计数模型之间的联系。我个人在实际操作中刷到这种“交叉验证”类题目时会特别兴奋它往往也是面试进入加分环节的信号。