LeetCode 136题：异或运算巧解“只出现一次的数字”

1. 读题先搞清楚这是道什么题1.1 题目真正在考察什么LeetCode上面的136题“只出现一次的数字”题目本身短得有点不像话给你一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现了一次的元素。看起来就是道简单题但我刷了这么多年题发现这题特别有意思。它虽然是“简单”难度却在面试里经常出现而且考的往往不是能不能做出来而是你用什么方式做出来。能AC的人一抓一大把但能用最优雅方式做出来的人可能不到十分之一。先说几个前提条件。第一数组非空也就是说不用考虑空的输入。第二只有一个元素是落单的其他所有人都是一对一对出现的。第三也是最重要的题目要求你实现线性时间复杂度的解法并且尽量不使用额外空间。很多人第一眼看到这题脑子里蹦出来的方案通常是暴力遍历、哈希表、排序。这三种方案都能做但如果你仔细抠题目会发现它真正的潜台词是能不能用一种线性的、不使用额外空间的算法把它解决了。这才是这题的核心考点。换句话说题目表面上在考数组和查找实际上在考验你对位运算的掌握程度。我自己的习惯是拿到一道题先不急着写代码先想想“如果我是出题人我想考什么”。136题出题人真正想让你意识到的东西就是异或运算的那几个性质。这些东西大学课本里都写过但真正遇到题目的时候能第一时间反应过来的真的不多。1.2 三种常规思路为什么总差那么一点先说最直观的思路。第一种暴力双重循环。遍历每个数再看它有没有其他相同的数复杂度O(n²)测试用例一大就超时。除非你只想练习语法否则基本不用考虑。第二种用哈希表/集合。把出现过的数存进集合重复出现的就删掉最后剩下的那个就是答案。或者用哈希表记录出现次数最后遍历找出次数为1的。这个方案时间复杂度O(n)空间复杂度也是O(n)能AC但不符合“不使用额外空间”的进阶要求。面试官很多时候会顺着这个思路继续追问能不能不用额外空间第三种先排序再遍历。排序后相同的数会相邻遍历一遍就能找到落单的数。时间复杂度取决于排序算法一般是O(n log n)排序本身可能还要额外空间比如归并排序。这条路同样不符合要求。我之所以把这三种都列出来不是让你们背下来当反面教材而是想说明一个道理在做题的时候你会走的弯路恰恰是理解最优解最好的垫脚石。正是因为哈希表需要O(n)空间、排序需要O(n log n)时间你才会意识到要同时满足“线性时间”和“常量空间”大概率需要某种暴力解法之外的技巧而这个技巧就是位运算。1.3 位运算思路是怎么想到的我第一次做这题的时候其实也没第一时间想到异或。我是先写了哈希表的解法然后提交通过了再看讨论区才发现有位运算的妙解。那一刻还挺震撼的因为代码就一行循环加一个异或赋值简洁得不像话。后来我养成一个习惯看到“出现两次”“成对出现”“找唯一”这种字眼脑子里就会自动拉响警报优先考虑异或。这跟肌肉记忆差不多见多了之后就会形成条件反射。思路是这样的两个相同的数异或的结果是0任何一个数和0异或的结果还是它自己。所以你只要把数组里所有元素挨个异或一遍所有成对出现的数字都会互相抵消变成0最后剩下的数字就是数组里那个唯一的、只出现了一次的数字。整个过程只需要遍历一次数组时间O(n)只需要一个变量存结果空间O(1)。干净利落满足所有要求。2. 核心细节异或运算如何一剑封喉2.1 异或的四个性质要理解这个解法异或运算的四个基本性质必须滚瓜烂熟归零律a ^ a 0。任何数和自己异或结果是0。恒等律a ^ 0 a。任何数和0异或结果还是它自己。交换律a ^ b b ^ a。异或运算和顺序无关。结合律a ^ b ^ c a ^ (b ^ c)。异或运算可以任意加括号。拿[2, 3, 2, 4, 3]举例。把所有数异或起来2 ^ 3 ^ 2 ^ 4 ^ 3因为交换律和结合律可以重排成(2 ^ 2) ^ (3 ^ 3) ^ 4两两抵消最后等于0 ^ 4也就是4。就这么简单。我之前给朋友讲这个解法的时候他说怎么感觉跟“消消乐”似的。我说这个类比很贴切两个一样的数字一碰就消失最后剩下的那个就是答案。背后的数学原理其实就是二进制的逐位运算但理解到“成对抵消”这个层面已经足够应付大多数场景。2.2 用生活场景理解异或去重从一个更直观的角度来看异或运算可以理解成“不带进位的二进制加法”。1 ^ 1 00 ^ 1 10 ^ 0 0你会发现它和二进制加法的区别只是不产生进位。这个性质在题目里可以这样理解数组里的每个数字都是成对出现的每一对在异或过程中都会抵消就像两个作用力相等方向相反的力相互抵消一样。因为所有成对的数据都是成对消失的所以落单的那个数字从头到尾都不会被抵消它就是最终结果。关键点在于异或运算不关心这些数字出现的顺序也不关心数字是正是负它只看二进制位上的值。这就是为什么它能用一个变量搞定不需要额外的数据结构。你不需要记每一个数字出现的次数只需要一个“累加器”把整个数组过一遍。2.3 时空复杂度完美满足要求这个解法的复杂度分析非常简单。遍历长度为n的数组每个元素参与一次异或运算时间复杂度就是O(n)。整个过程中只需要一个整数变量来保存累加结果不随输入规模变化空间复杂度是O(1)。这两条恰好精准命中题目的两个要求“线性时间复杂度”和“不使用额外空间”。所以这个解法在LeetCode的题目设定下可以算是最优解了。我经常看评论区发现很多人会用哈希表AC之后就不管了。这种学习方法其实有点可惜因为这题的位运算解法才是真正的精华。你花同样的时间如果只掌握了哈希表做法那你就错过了位运算这个面试中的高频考点后面刷到其他位运算题目可能还要重新摸索。3. 实操过程代码实现与踩坑记录3.1 Python版本最简洁的写法直接上代码def singleNumber(nums): res 0 for num in nums: res ^ num return res就这么几行。res从0开始遍历所有数字逐个异或最后返回res。我第一次看到这个解法的时候第一反应是就这对就这。但越是简单的东西背后的思考越不简单。如果要更“Pythonic”一点还可以用reduce一行写完但那样可读性反而变差了。我个人建议刷题的时候优先写清晰可读的版本面试的时候也一样能讲清楚思路比秀语法技巧重要得多。3.2 C和Java实现注意类型范围C版本几乎和Python一样class Solution { public: int singleNumber(vectorint nums) { int res 0; for (int num : nums) { res ^ num; } return res; } };Java版本也是同样的套路class Solution { public int singleNumber(int[] nums) { int res 0; for (int num : nums) { res ^ num; } return res; } }这三种语言写出来的东西本质上是一样的。唯一的细微差别是C和Java的int是32位有符号整数Python的int是任意精度整数。在这道题的范围里int完全够用但如果数字特别大Python不会溢出C和Java要小心边界值。好在这道题的输入范围是-2^31到2^31 - 1恰好是32位int的范围所以不会出问题。这里有个小细节值得注意C里用vectorint传参如果你传的是引用可以避免一次拷贝刷题这么写没问题。但如果是实际工程代码位运算的意图最好加个注释不然同事看了可能会一头雾水。3.3 JavaScript和Go的版本差异JavaScript也能用一样的思路但有一个隐藏的坑JS里的位运算是先把数字转成32位有符号整数来算再转回浮点数。对于题目给出的输入范围这个转换不会有问题但如果你自己加大数据量测试可能会遇到意想不到的结果。我建议用JS刷这题的时候就用官方给出的输入范围来测别自己去挑战超范围的值。var singleNumber function(nums) { let res 0; for (let num of nums) { res ^ num; } return res; };Go版本也很直接func singleNumber(nums []int) int { res : 0 for _, num : range nums { res ^ num } return res }总体来说这题的代码实现在所有主流语言里几乎不存在理解门槛。真正的门槛在于“你想不想得到用异或”。4. 常见问题与排查技巧实录4.1 用哈希表AC了但没达到进阶要求要紧吗很多同学问过我我用哈希表做出来了时间复杂度也是O(n)面试官会不会不满意我的看法是能AC说明你基础的解题能力没问题但如果你没体现出“优化”的意识面试官有可能会觉得你停留在“能跑就行”的层次。毕竟这道题明确写了进阶要求你看到了但没往那个方向想这本身就是一个信号。正确的回答思路是先讲清楚哈希表方案然后说“这个方案是O(n)时间和O(n)空间但题目要求尽量不用额外空间所以我再想一个更优的方案”然后引出异或解法。这样既展现了你掌握基础解法又体现了你追求更优方案的能力。4.2 异或能处理负数和0吗能而且处理得很好。二进制的异或运算是按位操作的和数字的正负没有关系。负数在计算机里以补码形式存储异或运算的时候直接按补码的每一位来算结果依然正确。0也是同理任何数和0异或都是它自己所以0不会影响结果。有同学担心“两个负数异或会不会因为符号位产生奇怪的结果”完全不会。你可以随便拿几个数手算验证一下或者自己跑一段代码用负数测试比如[-1, -1, -2]答案就是-2。4.3 边界情况有哪些容易踩的坑第一个就是数组长度。题目说数组非空但如果你在写通用工具函数最好还是加个空数组返回0或者抛异常的逻辑。不然传个空数组进去你的函数会返回0这个结果在数学上没有意义在工程代码里可能会导致bug。第二个是数组长度为1的情况。只有一个数的时候不用任何操作那个数就是答案。异或解法天然处理了这种情况因为res从0开始0异或任何数都等于它自身。第三个是重复数字不相邻的情况。比如[1, 2, 1]这种如果你用排序的思路排序后是[1, 1, 2]也能找到2。但如果你没排序直接在循环里做相邻判断就会出错。异或解法不受顺序影响所以完全没有这个问题。4.4 同类题型的排查经验做完136题之后你可能会碰到一个很迷惑的现象明明思路一样的题换个条件就不会做了。其实是因为异或解法只适用于“其他数字出现偶数次”的场景。所有数出现两次只有一个数出现一次用异或。所有数出现三次只有一个数出现一次异或就没那么好使了需要位运算配合状态统计。有两个数只出现一次其他都出现两次需要分组异或。遇到这些变体如果你还是死板地套136题的代码肯定做不出来。我一开始刷137题的时候也栽过跟头后来才意识到题目变了底层思路也得跟着变。136题是异或的“标准题”但异或只是整个位运算家族的冰山一角刷完136题之后后续的变体题同样值得花时间琢磨。5. 从这题延伸出来的位运算思考与刷题路线5.1 位运算在LeetCode中的典型应用场景136题刷完之后我建议你顺手做几道跟位运算相关的题形成体系。我自己刷下来感觉最值得做的是这几种类型判断奇偶性n 1比n % 2更快也更常见。交换两个数a ^ b; b ^ a; a ^ b。这个技巧面试偶尔会聊到。移除最后一个1n (n - 1)。在很多位运算题里都有奇效。判断是否为2的幂n 0 (n (n - 1)) 0。找出数组中只出现一次的数字也就是136题。把这些基础位运算技巧都过一遍你会发现很多“看起来需要用复杂数据结构”的题最后都能用几行位运算解决。这样你刷题的时候就会多一把钥匙。5.2 136题的后续变体题我刚才提到过几个变体这里重点说说。137题“只出现一次的数字 II”每个元素出现三次只有一个出现一次。这个题的解法就不能直接用异或了需要统计每一位上1出现的次数然后对3取模。本质上是用一个有限状态机去模拟“三进制”的进位有点绕但理解之后会对位运算认识更深。260题“只出现一次的数字 III”有两个元素各出现一次其他都出现两次。思路是先全员异或得到两个答案的异或值然后用这个异或值里的某个非零位把原数组分成两组分别异或就能得到两个数。第一次做的时候可能觉得“这也太巧妙了”但做多了就会明白这本质上是在利用异或结果中的信息做分组。这几道题如果全刷完你对位运算的理解会比大多数人深一大截。5.3 实际操作中的几个小建议刷题和做工程有一个很大的区别刷题的代码往往很短但优化的空间很大。我自己回刷136题的时候除了用最简单的异或解法还会刻意想想有没有其他写法、别的语言会不会有差异、能不能和HashMap解法做个对比测试。还有一个建议是“手算验证”。别光看题解拿着笔在纸上写几个小例子比如[2, 3, 2]或者[4, 1, 2, 1, 2]手动算一遍异或过程。这个过程会帮你把“异或抵消”这个概念从“好像懂了”变成“真懂了”。最后就是复杂度分析的表达能力。面试的时候不只是让你写代码还要你讲清楚思路。能把“为什么异或能找出唯一数字”讲得清清楚楚比闷头把代码写出来更重要。这也是我每次复盘这题都会反复练的东西。做这道题我最大的体会是它看起来简单但天花板其实很高。你可以用最简单的方式AC也可以顺着它一路刷到位运算的进阶题型。如果你刚开始刷LeetCode我建议从这题入手既能建立信心又能学到真东西。