刚刷到某在线题库的《136. 只出现一次的数字》时我觉得这题也就是个“遍历哈希”的小水题。直到我认真想了一遍“不用额外空间”这个附加要求才意识到这道题真正的分量藏在位运算里。题目描述很简单一个非空整数数组除了某个元素只出现一次以外其余元素都恰好出现两次找出那个只出现一次的元素。可恰恰是这个“其余都成对出现”的条件指向一个教科书级别的解法——异或。今天这篇文章我想把这题从暴力到最优、从原理到实操、从本题到经典变体完整拆开聊透并把我实际踩过的坑一并记录。无论你是刚入门算法还是面试前临时抱佛脚这篇都能帮你把“异或找单数”这个套路彻底焊进脑子里。1. 先别急着写代码这道题真正在考什么1.1 题目条件里藏着的关键线索题目给出三个硬性条件非空数组、一个元素出现一次、其余元素每个都出现两次。目标是在O(n)时间内找到那个“孤狼”元素。很多人第一反应是哈希表遍历数组把每个数字作为键出现次数作为值最后再扫一遍哈希表找出值为1的键。这样写法本身没错时间复杂度也是O(n)但问题在于空间复杂度。最坏情况下哈希表要存储 n/2 个键值对随着数组规模增长内存占用线性膨胀。题目虽然没有像某些要求那样把“不使用额外空间”写进题面但作为经典题最优解从来都是冲着O(1)额外空间去的。排序法也能做先排序再遍历找相邻不相同的元素。但排序的复杂度通常是O(n log n)如果调用系统排序内部使用的额外空间也不固定并不满足“高效找单数”的精神。所以从题目条件反推最核心的线索在于“重复元素出现两次”这个结构本身。两个相同的数字放在一起能不能通过某种运算直接抵消这才是这题真正想考察的思维转换。1.2 从“统计次数”到“运算抵消”的思路转折统计次数的思路是“加法思维”我想知道谁出现了一次那就记下所有元素各自的次数。而位运算给出的是一条完全不同的路既然a和a成对出现那我能不能定义一种运算让相同的两个数字在一起恰好归零并且这个运算还满足交换律不受数组顺序影响这个运算就是异或XOR符号写作^。异或的规则很朴素两个二进制位相同则结果是0不同则结果是1。放到整数层面看就是“按位异或”。它有一条极其重要的性质任何整数与自身异或结果是0任何整数与0异或结果仍是它本身。于是只要把所有元素从头到尾异或一遍成对的数字全部消成0最后剩下的就是那个只出现一次的数字。整个过程只需一个变量额外空间是O(1)时间复杂度是遍历一遍的O(n)。这个思路之所以漂亮在于它没有去“数次数”而是利用了“成对抵消”的数学结构——这才是出题人真正希望看到的思维能力。2. 异或的底层逻辑为什么它能精准抓住“只出现一次”2.1 异或的三条核心性质异或运算有三条性质是理解这题的基础。第一交换律和结合律a ^ b等于b ^ a(a ^ b) ^ c等于a ^ (b ^ c)。这意味着运算顺序不影响最终结果我在遍历时从哪头开始算都行。第二自反性a ^ a 0这是“成对抵消”的根基。第三零元a ^ 0 a任何数异或0都不改变。有了这三条针对数组[2, 3, 2]运算过程就是2 ^ 3 ^ 2。由于交换律和结合律可以重排为(2 ^ 2) ^ 3先按自反性得到0 ^ 3再按零元性质得到3。整个过程你可以完全不关心数字出现的先后顺序这是哈希表统计需要额外扫描做不到的优雅。2.2 按位运算的独立性异或之所以适用于整数数组是因为整数在计算机内部用二进制表示异或运算是一个“按位独立”的运算。也就是说两个数异或时第k位的结果只取决于两个数第k位的值与其他位无关。不用考虑进位不用考虑符号扩展的连锁反应每一位都是单独的0/1判断。比如十进制的5二进制0101和3二进制0011异或结果是6二进制0110。具体看最高位的0和0异或得0第二位1和0异或得1第三位0和1异或得1最低位1和1异或得0。正是因为按位独立所以两个“相同”的数字异或时它们的每一位必然都相同结果每一位都是0整体就是0。两个不同数字异或时结果是它们二进制差别的“记录器”——不同位是1相同位是0。这为后面的变体题比如找出两个只出现一次的数字埋下了伏笔。2.3 用灯光开关来建立直觉很多初学者觉得异或抽象。我会用“灯光开关”来类比假设有一排开关每个数字代表一次操作。开关的规则是“拨一下改变状态再拨一下回到原状”。遍历数组里的数字就相当于对对应的开关依次拨动。出现两次的数字拨动两次开关回到初始状态出现一次的数字拨动一次开关状态保持为“已改变”。最后统计哪些开关还处于改变状态就能找出只出现一次的数字。这个类比虽然不是完全精确但对建立运算直觉很有帮助。实际编码中你不需要维护一排开关只需要一个变量不停执行ans ^ nums[i]就行了。这个变量就像一个计算器把当前遍历过的数字按位“混合”起来重复出现的数字在混入两次后自动归位只出现一次的数字最终在这个变量里留下完整痕迹。3. 实操落笔从最小实现到多语言版本3.1 核心算法一行的极简解法如果你脑子里的异或思路已经清晰代码几乎不长于一行主逻辑。我用 Python 写下标准解法def single_number(nums): ans 0 for num in nums: ans ^ num return ans初始化ans 0很关键因为0是异或的零元不会干扰结果。遍历过程中每个元素一次异或成对的全部抵消。这个版本的时间复杂度是O(n)空间是O(1)通过了大数据量的测试。如果偏爱函数式写法也可以用reduce把整个数组折叠成一个值from functools import reduce def single_number(nums): return reduce(lambda a, b: a ^ b, nums)这行式写法本质是一样的就是按顺序对数组中所有元素做异或。对刚开始学位运算的朋友我更推荐写显式for循环版本因为逻辑一目了然面试时也好解释。3.2 再写几种主流语言版本这题几乎每种语言都有对应实现差异只在语法层面。C语言版本int singleNumber(int* nums, int numsSize) { int ans 0; for (int i 0; i numsSize; i) { ans ^ nums[i]; } return ans; }Java版本class Solution { public int singleNumber(int[] nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; } }JavaScript版本var singleNumber function(nums) { return nums.reduce((acc, num) acc ^ num, 0); };这里有个容易忽略的细节不同语言对整数的底层表示不同比如JavaScript的位运算会先把操作数转为32位有符号整数再执行异或最后再转回64位浮点数。对于这道题的普通取值这没问题但如果数组里混入了一些绝对值极大的数就要留意底层的32位截断行为。后面我会在踩坑部分专门展开。3.3 边界条件与特殊值检查实际提交时题目保证数组非空且必有一个只出现一次的元素但在本地测试或面试追问时最好把边界情况都过一遍。单元素数组[7]是最容易忽略的输入初始化ans0执行0 ^ 7结果是7直接正确。负数和零也完全不受影响因为异或是按二进制位操作负数的符号位也参与运算两个相同的负数异或后每一位都相同照样抵消成0。我一直建议写完代码后在本地至少跑3组测试全为正数的常规数组、包含负数与零的数组、长度为1的数组。它们能帮你确认实现不是只针对样例数据生效。3.4 一道题里的工程思维虽然这是算法题但我会把“变量初始化”“遍历终止条件”“结果返回”看成一个小型工程流程。初始化时选0是遵循异或零元遍历时不做任何剪枝是为了保证不会漏元素返回时直接返回累计结果没有中间转换。这段代码的测试重点不在语法而在“多次运行结果是否稳定”。我自己就试过把同样的逻辑用标准库的accumulate重写结果行为完全一致这进一步验证了异或结合律的正确性。看一行代码很爽但理解并证明每一步设计才是一次刷题真正的收获。4. 从一道题长出一片题目异或思路的经典变体4.1 变体一其余元素出现三次怎么办异或能处理“出现两次”的核心在于a ^ a 0。如果题目改成“其余元素都出现三次”异或就失效了因为三次异或后不等于0a ^ a ^ a a。这时需要从“按位计数”的角度想只看某一位把所有数字的该位加起来对3取模余下的就是只出现一次的数字在该位上的值。实现上可以维护两个变量ones和twos分别记录“出现一次”和“出现两次”的位状态。标准写法出自数字电路里的有限状态机思路def single_number_three(nums): ones 0 twos 0 for num in nums: ones (ones ^ num) ~twos twos (twos ^ num) ~ones return ones这段代码初看很绕核心过程是如果某个位从没出现过twos对应位为0新数字来了就记录进ones如果ones里已经有这个位新数字来了就把它从ones移除并进twos如果twos里也已经有这个位新数字来了就把它从twos移除。三个相同数字会完整走完“进ones-转移到twos-清除twos”的循环最终归零。只有出现一次的数字会停留在ones里。实际跑这题时建议用一个[2, 2, 3, 2]的样例逐位模拟能很快理解状态机的行为。4.2 变体二两个只出现一次的数字另一道知名变体数组里恰好有两个数字只出现一次其余都出现两次。如果直接全部异或得到的是两个目标数字的异或结果x ^ y。关键在于如何把这两个数字分开。由于x ^ y不为0它至少有一个二进制位是1这个1的位置说明x和y在该位不同。用这个位把整个数组分成两组该位是1的进一组该位是0的进另一组。每组内部所有成对数字依旧成对而x和y被分到了不同组。分别对两组做异或就得到了两个答案。找分组位有个常用技巧def single_number_two(nums): xor_all 0 for num in nums: xor_all ^ num diff xor_all (-xor_all) ans1 0 ans2 0 for num in nums: if num diff: ans1 ^ num else: ans2 ^ num return [ans1, ans2]这里的xor_all (-xor_all)是“取最低位1”的经典写法。它利用了负数在计算机中的补码表示一个数的负数等于按位取反再加1。两者按位与结果只会保留原数最低位的那个1其余位都是0。这个技巧在后续很多位运算题中都会反复出现建议直接背下来。4.3 变体三缺失的数字题目给一个包含[0, n]中n个不同数字的数组找出缺失的那个。这也可以从异或角度切入初始化结果为n然后对索引和数组元素同时异或。因为完整的[0, n]序列和缺失数组只差一个数字所有成对出现的索引/数字会被抵消最终剩下缺失值def missing_number(nums): ans len(nums) for i, num in enumerate(nums): ans ^ i ans ^ num return ans我最初看到这个写法时愣了几秒因为在同一个循环里异或了索引和值。但只要跟着两条线走一遍[0, 1, 3]就会发现0和1都正好出现两次3只剩一次缺失的2就自然而然地留在了ans里。这个变体最值得学习的地方是异或不仅能处理“成对抵消”还可以“对完整序列和缺失序列做异或找出差异”。4.4 变体规律总结刷了这些变体后我归纳出一个很实用的判断标准看到“成对出现”“找唯一”“找差异”第一反应就应该是异或看到“出现多次且计数取模”第一反应是位计数状态机看到“两个唯一数字”第一反应是分组异或。下表是我自己整理的对照参考题目特征核心思路空间复杂度一个唯一其余成对全数组异或O(1)一个唯一其余三份位计数状态机O(1)两个唯一其余成对全异或后按位分组O(1)缺失数字序列异或找差异O(1)把这张表记在脑子里以后再遇到所谓“新题”很多都能一眼看穿本质。5. 踩坑记录与排查心得5.1 初始选项别乱选我第一次写这题时曾想用ans nums[0]做初始化然后从索引1开始遍历。逻辑差不多但会多一个“数组一定非空”的前提判断。后来我统一改成ans 0再全遍历。理由很简单0是异或零元初始化成0可以让代码天然处理空数组和单元素数组不用额外条件分支。这个习惯在后来的变体题中帮了不少忙因为很多变体题也沿用同样的初始化方式一旦不用判断边界代码整体的鲁棒性就上去了。5.2 负数与零真的不用怕有朋友私信问我“异或遇到负数会不会出问题”这是个很自然的担忧因为十进制里负数看着有符号。但在计算机内部负数以补码形式存储异或操作根本不去理解“正负”它只按位操作。两个相同负数补码每一位完全相同异或后每一位都是0结果就是0。零参与异或同理0 ^ x x正好利用零元性质。我曾经在某个32位平台上调试一个很大的负数输入结果发现完全没问题才彻底放心。这里有一个人为安全提示如果你用的语言对“无符号整数”和“有符号整数”区分严格要留意赋值时的类型转换因为不同编译器/解释器对高位符号位的处理方式略有差异。5.3 长数组与整数溢出陷阱异或本身不会溢出因为它只是按位操作不产生进位。但是使用某些语言时隐含的类型转换可能引入意外行为。比如JavaScript的位运算会把数字先转换为32位有符号整数当数组中的整数超过这个范围时计算会截断。另外如果题目描述中允许数据接近2^31量级在C语言里用int没问题在Python里用int也安全因为Python的整数是任意精度。真正容易踩坑的是把数组元素累加或做其他算术运算的解法——那个确实可能溢出异或解法反而规避了这个风险。5.4 面试现场最容易翻车的三个细节第一个细节只写代码不解释初始化。面试官问“为什么ans初始化为0”如果你只说“因为大家都这么做”会扣分。正确回答是“因为0与任何数异或都不改变值它是个零元不会引入额外信息”。第二个细节忘记证明为什么成对数字抵消。你要明确说“a ^ a 0这是异或自反性”。第三个细节写完代码不做样例推演。哪怕在脑子里跑一遍[4, 1, 2, 1, 2]也能快速自查。很多面试者不是不会异或而是不会边写边讲结果明明正确的解显得像背答案。5.5 实测性能与阅读源码的体会我自己在本地用生成长度100万的数组做过一次简单计时。哈希表解法因为要维护字典耗时约40毫秒左右异或解法耗时不到3毫秒。差距主要来自内存分配和哈希计算。空间上哈希表方案在极端情况下内存占用可能达到数十MB而异或方案就是固定8字节或4字节取决整数位数。这种差异在刷题平台上看不出什么但放到真实嵌入式或高性能场景中就是天壤之别。我把这道题的标准解法和标准库聚合函数做过对比结果一致这让我更敢在生产代码里使用位运算做重复项检测只要逻辑注释写清楚维护难度并不高。我个人在实际操作中的体会是位运算的魅力不在于“炫技”而在于它能把一个看似需要额外容器的问题压缩成一个变量。136. 只出现一次的数字这道题表面上是刷题模板实际上是理解异或、理解二进制表示、理解“成对抵消”这个思维的绝佳入口。把它刷透之后再去碰缺失数字、重复数字、分组异或那些变体你会发现自己不是在背题而是在用同一把钥匙开不同的锁。学习算法最值得的收获不是AC那一下的快感而是这把钥匙在你脑子里逐渐成型的过程。