1. 内容整体设计与思路拆解1.1 为什么这两道题值得放在一起刷我在刷力扣热题100的时候发现一个规律真正的高频面试题往往不是那种绕来绕去的难题而是看起来平平无奇、却恰好能卡住一批人的题目。136和169就是典型代表一个考察位运算一个考察贪心思维都是《剑指Offer》级别的常客也是面试官最喜欢用来做“筛选题”的题目。先说结论这两道题最优雅的解法都逃不开“线性时间常数空间”这个要求。你可能会觉得这有什么难的HashMap一开问题不就解决了吗但恰恰是这一点把很多人挡在了门外——面试官要的不是“做出来”而是“在限定条件下做出来”。136题要求时间复杂度O(n)、空间复杂度O(1)169题同样如此。这个限制条件一出来哈希表这条路直接堵死逼着你去找更底层的规律。这两道题放在一起刷还有一个特别的好处它们都能让人学会“从数据本身的性质出发想问题”。136题的数据是成对出现、只有一个落单169题的数据是某个元素出现次数超过一半。这两个描述看似无关但背后都指向同一种思维——不要急着遍历存储先想想数据有没有什么“算术性质”可以利用。1.2 考察的本质不是让你暴力解我见过不少刷题新手拿到136题第一反应就是“排序然后看相邻元素”拿到169题第一反应就是“排序后取中间那个”。排序确实是解法而且能通过但时间复杂度从O(n)变成O(nlogn)空间复杂度也从O(1)变成O(logn)某些排序实现这跟题目要求的“线性时间”已经不是一个量级了。面试官出这两道题其实想考察的是三件事你知不知道位运算的基础性质。异或运算满足交换律、结合律相同数异或为0任何数与0异或还是它本身。这三个性质叠加起来就是136题的完整答案。你有没有想过“消去”而非“记录”。很多人在处理“找不同”类问题时第一反应是“用哈希表记录出现次数”但136题的经典解法其实是在“让成对的元素互相抵消”。这种思路一旦打通以后遇到类似题目会快很多。你是否理解贪心/对抗思想在数据上的表达。169题的摩尔投票法本质上是让不同元素互相消耗最后剩下来的那个就是答案。它不要求你记住每个元素的次数只要求你关注“谁留下”。1.3 解法全景图从暴力到最优先把两道题的所有主流解法摆出来后面再逐个拆解。这样你心里先有个全局不会在看完一种解法后就不再往下想了。题目解法时间复杂度空间复杂度是否满足题意136 只出现一次的数字双层循环暴力计数O(n^2)O(1)否136哈希表统计O(n)O(n)否136排序后扫描O(nlogn)O(1)或O(n)否136异或运算O(n)O(1)是169 多数元素哈希表统计O(n)O(n)否169排序取中间值O(nlogn)O(1)或O(n)否169摩尔投票法O(n)O(1)是这个表格一眼就能看出最符合题意的解法往往不是第一个蹦进脑子里的那个。接下来我分别把这两道题掰开揉碎讲清楚每一步的“为什么”。2. 核心细节解析与实操要点2.1 136题异或运算为什么能“凭空”找出落单的数先看问题描述给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现一次的元素。“其余每个元素均出现两次”——这句话是整道题的钥匙。它暗示了一个非常强的性质这个数组里所有的数都可以被配成一对一对的。既然能配对那配对之后“消失”就是很自然的需求。怎么让一对相同的数消失异或。异或运算XOR的规则表是相同为0相异为1。这导致它有一个极其重要的性质a ^ a 0。同样一个数跟自己异或结果必定是0。另一个性质是a ^ 0 a任何数与0异或结果还是原数。再加上异或满足交换律和结合律于是数组里所有数进行异或成对的数会变成00之间继续异或还是0最后剩下的就是那个落单的数用生活里的事情来类比就好比一群人两两牵手走进会场最后还站在门口的那个就是多出来的。异或运算就是那个“牵手检查器”牵过手的直接放行没被牵走的自然暴露。2.2 136题代码实现与逐步推演代码极其简短但每行都值得展开说。我用三种语言各写一版因为面试现场你未必能选自己最熟的语言。// Java class Solution { public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } }# Python class Solution: def singleNumber(self, nums: List[int]) - int: ans 0 for num in nums: ans ^ num return ans// C class Solution { public: int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } };拿一个例子手推一遍。假设输入是[4, 1, 2, 1, 2]ans初始为0ans ^ 4得4ans ^ 1得5二进制0101ans ^ 2得7二进制0111ans ^ 1得6二进制0110因为0101 ^ 0001 0100再^00100110? 重新算4^155^277^166^24。最终答案是4正确。这里的每一步都不需要你“记住”当前ans代表什么只需要相信异或运算的规则就好。这也是位运算的魅力所在它不需要状态存储不需要额外容器纯粹靠运算律就把结果“算”出来了。注意这里有个坑——任何数异或0等于它本身所以ans初始化不能是1或者别的值必须是0。这一点写代码时容易忽略一旦初始化错结果全错。2.3 169题摩尔投票法的核心思想再看169题的问题描述给定一个大小为n的数组找到其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。要求同样是O(n)时间、O(1)空间。哈希表确实可以数次数但空间不达标。既然不能用额外空间那就要换个角度想这个数组里有个元素“特别多”多到超过所有其他元素加起来的总和。这个“超过总和”的特性可以用来做“互相抵消”。摩尔投票法的思路其实非常直白把不同元素想象成两个阵营的士兵两两相遇就同归于尽。因为某个阵营人数超过一半最后活下来的那个士兵必然来自这个阵营。具体做法用一个变量candidate记录当前“候选多数元素”再用一个变量count记录它的“净存活人数”。遍历数组。如果count 0就把当前元素设为新的candidatecount设为1。如果当前元素等于candidatecount加1否则count减1。遍历结束后candidate就是那个多数元素。这里有个很关键的直觉问题为什么count减到0时重新选candidate最终剩下的candidate一定正确可以用反证法想假设存在一个真正的多数元素X它的出现次数超过n/2。那其他非X元素的总次数不到n/2。想象整个遍历过程是一次“配对抵消”每个非X元素都会消耗掉一个X的“票数”但X的票数总量始终比对手多所以就算中间被消耗到0下一次遇到X时X会重新成为candidate并且最终以正票数胜出。2.4 169题代码实现与边界处理同样给出三种语言实现// Java class Solution { public int majorityElement(int[] nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; } count (num candidate) ? 1 : -1; } return candidate; } }# Python class Solution: def majorityElement(self, nums: List[int]) - int: candidate 0 count 0 for num in nums: if count 0: candidate num count 1 if num candidate else -1 return candidate// C class Solution { public: int majorityElement(vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; } count (num candidate) ? 1 : -1; } return candidate; } };手推一遍假设输入是[3, 2, 3]。candidate0count0遇到3count0所以candidate3count1遇到22 ! 3count变为0遇到3count0所以candidate3count1最终candidate3正确再看一个边界情况[1, 1, 1, 2, 2]。按算法走candidate会经过1、1、1count从1到2到3遇到2减到2遇到2减到1最终candidate1正确。在这个例子中count从未归零候选一路稳定到底。这里有一个容易误解的点摩尔投票法得到的candidate只是在“存在多数元素”的前提下有效。如果题目没有保证存在多数元素你需要额外遍历一次验证candidate是否真的出现次数超过n/2。力扣这题已经保证了存在所以可以直接返回。3. 实操过程与核心环节实现3.1 从读题到写码一个可复制的四步流程我在面试别人和被别人面的过程中总结出一个特别实用的读题套路拿到算法题之后不要急着写代码按这四步来第一步圈出数据范围。136题要求“其余元素均出现两次”169题要求“出现次数大于n/2”。这些数字特征决定了能用的解法。第二步看时空限制。如果题目说“不适用额外空间”或者“空间复杂度O(1)”那哈希表基本不用考虑了。第三步想“数据本身会不会自相抵消”。有没有成对的有没有过半的这些性质能不能用运算表达第四步写代码前先在草稿纸上推一遍小例子。用小数组验证思路确认没有逻辑漏洞再落代码。面试的时候很多人大脑一片空白是因为跳过了第一步和第三步直接去回忆有没有做过类似的题。这样等于把主动权交给了运气。按流程走即使没见过原题也能顺着数据性质推导出正确解法。3.2 136题的完整推导过程136题从读题到最优解我们可以完整走一遍读题发现“出现两次”这四个字马上联想到异或的性质。如果你对异或不熟先在白板上写出三条性质a ^ a 0 a ^ 0 a a ^ b ^ a (a ^ a) ^ b 0 ^ b b这三条摆在桌子上后面写代码就水到渠成了。接下来代码只需要一个循环ans 0 for num in nums: ans ^ num return ans写完后不要急着交建议手动跑两个用例用例A[2, 2, 1]期望1用例B[4, 1, 2, 1, 2]期望4把这两个用例在纸上推完再提交代码。你会发现代码虽然短但通过率几乎100%因为逻辑足够简洁、不容易有分支错误。3.3 169题的完整推导过程169题从读题到最优解的推导可以按这个节奏走先想最暴力的思路双层循环每一轮数一数某个元素出现了几次时间复杂度O(n^2)太慢。次之是哈希表O(n)时间但O(n)空间。排序取中间O(nlogn)时间。这些都是合理但不够优的方案。然后引入“对抗抵消”的思想既然那个元素占了一半以上那我用一个变量记录“当前候选者”一个变量记录“票数差”让不同的元素互相抵消。这个思想初看不严谨但仔细想就会发现它是基于“严格过半”这个条件成立的。代码candidate 0 count 0 for num in nums: if count 0: candidate num count 1 if num candidate else -1 return candidate这里我想特别强调一个实操细节为什么count归零时要更换candidate而不是继续保留旧candidate因为count归零意味着之前的candidate已经被完全“抵消”了在当前这个子区间里它并不占优势。我们不可能在遍历过程中预知未来的元素唯一可靠的做法是哪个元素让count重新“活”起来就让它成为新的候选。这正是摩尔投票法优雅的地方——它不需要回头只需要向前。3.4 测试用例设计与边界验证算法题能不能一遍过很大程度上取决于测试用例想得全不全。我给自己定了一个规矩每道题至少设计三类用例——常规用例、边界用例、极端用例。对136题用例类型输入期望输出说明常规[2,2,1]1基本场景常规[4,1,2,1,2]4多个成对元素边界[1]1数组长度为1极端[-1,-1,3]3包含负数极端[1,1,1,1,2]2多个重复仍只有一个落单对169题用例类型输入期望输出说明常规[3,2,3]3基本场景常规[2,2,1,1,1,2,2]2多数元素在尾部边界[1]1单元素数组极端[1,1,1,2,2]1多数元素恰好刚过半极端[6,6,6,7,7]6交替出现把这些用例在草稿纸上跑一遍比直接在力扣上提交碰运气要靠谱得多。面试官最喜欢看到的就是候选人主动设计测试用例、自测通过后再交代码这比写对代码本身还能加分。3.5 复杂度分析怎么在面试中把话说清楚面试中写对代码后还有一个必答题分析时空复杂度。很多人把“时间复杂度O(n)、空间复杂度O(1)”背下来就完了但面试官接下来会追问“为什么”。136题的空间复杂度为什么是O(1)因为我们只用了ans这一个额外变量它的大小不随输入规模n变化。不管数组里有10个元素还是一亿个元素我们的额外空间永远是固定的。这跟哈希表方案对比鲜明——哈希表需要存储最多n个键值对空间随n线性增长。169题的空间复杂度同理candidate和count都是固定数量的额外变量。而时间复杂度O(n)的来源是遍历了一遍数组每一步操作都是常数时间的异或或比较加加减减跟n的大小呈线性关系。这个解释比单纯报一个“O(n)”要有说服力得多。我在面试中观察过能把这个说清楚的人基本都能进入下一轮。4. 常见问题与排查技巧实录4.1 136题异或解法踩坑记录坑一ans初始化错误。有人习惯把结果的初始值设为nums[0]然后从i 1开始循环。这样写其实也行但如果数组是空的就会出问题。我把这个坑讲出来是因为我见过好几个候选人写成了int ans nums[0]然后直接遍历整个数组把nums[0]又异或了一遍。如果那个数字恰好是落单的元素结果就变成了0。坑二没理解异或的交换律。异或运算里a ^ b和b ^ a结果一样所以数组中元素的顺序完全不影响最终结果。这其实是个优点意味着我们不需要对数组做任何预处理。但有些人会在脑里想“会不会跟顺序有关”然后陷入自我怀疑。实际上异或运算是“按位”的每一位独立计算与顺序无关。坑三误以为异或只能处理正整数。其实负数、0也都适用因为异或本质上是二进制补码层面的运算。力扣的测试数据也经常包含负数只要理解到位完全不需要为负数做额外处理。4.2 169题摩尔投票法边界排查边界一count为0之后的下一次遍历。count归零后新指向的元素会成为新candidate这看起来像“突然变心”但其实算法要求的就是这个。很多人在写代码时容易纠结写成“count归零但candidate保持不变”结果得到错误答案。记住规则count0时无条件换成当前元素。边界二数组长度为1。只有一个元素时candidate就是这个元素count1直接返回即可。这个边界最容易通过但也最容易在测试时忘记。边界三多数元素恰好刚超过一半。比如[1, 1, 1, 2, 2]1出现3次刚好超过n/22.5。这种情况摩尔投票法依然成立。如果不放心可以多跑几组类似用例验证。边界四题目不保证存在多数元素时怎么办。力扣169题明确说了“你可以假设数组是非空的并且给定的数组总是存在多数元素”所以这题可以放心直接返回candidate。但很多面试官会延伸提问“如果没有保证呢”这时候你要能说出二次遍历验证candidate出现次数是否真的大于n/2。这是加分项能体现思维的严密性。4.3 快速排查表现场debug的思路如果代码跑出来出错不要盯着屏幕干瞪眼按这个顺序排查先检查初始化ans和candidate初始值对不对count初始值是不是0再检查循环内分支136题只有一个异或操作出错的概率极低169题有count0分支检查是不是把判断条件写成了count 0而不是count 0。注意count 0的情况在实际操作中不会出现因为只要count降到0就重新设candidate了。最后推演一个小例子拿[1, 2, 1]这种短数组在纸上逐步写出candidate/count变化和代码运行结果对比。这个方法可以帮你把90%的错误定位到具体某一行。4.4 独家技巧如何从136题迁移到169题很多人刷题是“一道一道”刷的刷完就忘了。我这里讲一个我的独家技巧刷完一道题强制自己联想起至少一道同类型的题。136题本质是“出现偶数次的都消失留一个出现奇数次的”。那如果推广到“出现三次的消失留一个出现一次的”呢这就是力扣137题。它的解法是统计每一位上1出现的次数然后对3取模。思路依然是“利用数据自身出现的次数规律”只是从异或变成了按位统计取模。169题本质是“有元素超过半数”。推广一下“有元素出现次数超过三分之一”呢那就是力扣229题摩尔投票法的升级版要用两个candidate。这些题都是同一棵树上的果子理解了根果子随便摘。5. 延伸拓展位运算与投票法的变体5.1 位运算家族136到137、260的进化路线136题的异或解法只是位运算的冰山一角。我把这几道题放在一起你看下它们之间的关系136所有数出现2次1个数只出现1次。解法全数组异或。137所有数出现3次1个数只出现1次。解法统计每个二进制位上1的个数对3取模。260所有数出现2次2个数只出现1次。解法全数组异或后找到结果中任意一个为1的位将数组分成两组每组各自异或。从2次到3次从1个落单到2个落单本质上都是“利用出现次数的周期性”。这就像时钟一样分针走一圈回到原点但如果你记录的是“走了多少圈”就能发现异常。位运算的每个bit就是一个时钟统计每个时钟走完几圈然后取模剩下的就是落单者。这个思想如果你看懂了再回头去看136题就会有一种“降维打击”的感觉——你不再只是背答案而是真正理解了这一类题的骨架。5.2 摩尔投票法家族169到229的进化路线169题是单候选人的投票法229题是双候选人的投票法。229题要求找出所有出现次数超过n/3的元素。这样的元素最多有2个所以要用两个candidate和两个count。算法大致是维护candidate1、count1、candidate2、count2。遍历数组按一定规则更新这两个候选人。最后验证两个候选人是否真的出现次数超过n/3。这个变体在面试中出现频率不低算是169题的自然延伸。面试官出一个169然后追问“改成三分之一怎么做”核心就是想看你有没有真正理解摩尔投票法的“对抗抵消”内核而不是只会背代码。5.3 这些思想在真实工程里有什么用有人可能会问我学了异或和投票法除了刷题还有什么用异或运算在工程里最常见的应用是数据校验和纠错。比如RAID硬盘阵列就利用了异或校验把多个硬盘的数据进行异或存储一份校验信息当某块硬盘损坏时可以通过其他硬盘和校验信息把数据恢复出来。这就是因为异或运算的“可逆性”——a ^ b ^ b a损坏的数据像那个“落单的数”一样被找回来。摩尔投票法的思想在分布式系统里也有影子。比如在选举共识算法中节点之间需要选出“多数派”来达成一致而多数派的定义就是超过一半节点。虽然实际的共识协议复杂得多但“过半数者胜”这个直觉是相通的。6. 实操总结与进阶建议6.1 我刷完这两道题后的真实体会我第一次刷这两道题的时候其实是先试了哈希表。毕竟哈希表好想好写谁不想走捷径呢但后来面试官一追问“空间复杂度”我才意识到自己只是“会做题”不是“会解问题”。直到我把异或和投票法真正看懂、能手推证明才感受到算法的美感所在。有一个习惯我现在还在用每刷完一道力扣题我会把这道题的最优解、次优解、暴力解分别写一遍然后自己在评论区或笔记里写一段“为什么最优解能成立”的证明。这个过程比刷十道新题还管用。因为很多人卡住的不是代码而是“看不懂为什么对”。6.2 面试答题的加分技巧面试时代码写完不是终点。我建议按这个顺序表达先说暴力解哈希表或排序快速建立正确性。再分析暴力解的不足空间O(n)或时间O(nlogn)。然后提出最优解用一句话讲清楚核心思路。最后手推一个小例子证明思路可行。最后分析复杂度并回答追问如“如果没有保证多数元素怎么办”。这套流程15分钟内能走完但给面试官留下的印象远比“15分钟静默写代码然后说写完了”要深刻。说白了力扣刷题不只是为了过题更是为了训练自己“清晰地表达一个复杂问题解决方案”的能力。6.3 后续可以继续刷的题目如果你被这两道题勾起了兴趣建议按照这条路线继续巩固初级巩固136、169、191位1的个数、2312的幂。中级进阶137、260、229、268缺失数字。高级挑战421数组中两个数的最大异或值、477汉明距离总和。尤其推荐137和260它们和136形成一个完整的“位运算找落单”系列刷完你会发现自己的位运算能力上了一个台阶。而229则能帮你把摩尔投票法从“会一道题”变成“会一类题”。最后分享一个小技巧以后遇到任何“找唯一”“找多数”“找缺失”类问题先问自己一句——“这组数据里有没有什么周期性或对抗性可以利用”这个问题只要问出来了你离最优解就不远了。