企业官网建设流程全解析

在力扣（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的最优解是异或（XOR），169的最优解是Boyer-Moore投票（摩尔投票）。它们本质上都是“抵消”的思维。异或是同一数字与自己抵消为0；摩尔投票是候选人的票数被“反对票”抵消。学会这两种抵消模型之后，你会发现它们能延伸拓展出一大批题目，比如137. 只出现一次的数字II、260. 只出现一次的数字III、229. 求众数II等等。所以把这俩一起刷，性价比极高。

1.2 四类解法路线，提前理清思路

我以前刚开始刷题的时候，遇到这种数组统计问题，第一反应往往是开一个哈希表，然后把元素一个个塞进去，最后遍历哈希表找答案。这当然能做，而且136和169都能用哈希表直接解。但哈希表的空间复杂度是 O(n)，136的进阶要求不允许，169的进阶要求也不允许。这就倒逼你去想优化方案。

我把两道题的常见解法路线画成一张对照表，你一眼就能看清各自的定位：

注意看，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 异或解法完整推导、代码与边界验证

写代码之前，先把流程固定下来：

1. 初始化一个变量 result = 0。
2. 遍历数组中每个元素 num，执行 result = result ^ num。
3. 遍历结束后返回 result。

翻译成Python代码长这样：

def singleNumber(nums): result = 0 for num in nums: result ^= num return result

如果你在LeetCode上提交，这个解法通常能跑进最佳区间，代码量还极短。我见过不少新手在这里犯两个小错。第一个是习惯把result初始化成数组第一个元素，然后从第二个元素开始异或——这样结果一样，但如果数组为空就会出问题。虽然题目说“非空数组”，但写代码时保持result=0的写法更严谨，也更好理解。第二个错误是容易把异或符号和幂运算混淆。Python里异或是^，不是**；C++/Java里也是^，不是xor（C++确实有关键字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。遍历到每个元素时：

1. 如果差额等于0，当前元素顶替成为新候选人，差额设为1。
2. 如果当前元素等于候选人，差额加1。
3. 如果当前元素不等于候选人，差额减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；若两张都不是M，M的比例只会相对变高。所以无论删除顺序如何，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 常见错误和初学者误区速查

下面这张表是我自己刷题加看评论区总结出来的高频错误，每一行都对应过真实案例。

这里有一个非常典型的“看着对，其实不对”的例子：有的同学实现摩尔投票时，把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)的方案，说明这两道题在你这里已经不仅靠背代码，而是真正建立起了位运算与计数模型之间的联系。我个人在实际操作中刷到这种“交叉验证”类题目时会特别兴奋，它往往也是面试进入加分环节的信号。