这道只出现一次的数字LeetCode 136几乎是所有算法入门者都会碰到的一道经典题也是我在面试别人时最爱用来做热身的一道题。题目本身不复杂但往里挖的深度远超想象从哈希表的常规解法到异或运算的极致解法再到如果重复三次怎么办如果有两个只出现一次的数字呢一个题目能串起位运算领域里大半的核心知识点。这篇文章就围绕这个题目把我实际刷题、面试、复盘过程中积累的解决思路、变体扩展和踩坑经验完整梳理一遍希望能给正在啃算法的朋友一些参考。1. 题目解读与整体思路拆解1.1 题目最早是怎么来的这个题目在LeetCode上是136号题面非常简短给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。题目要求线性时间复杂度并且最好不使用额外空间。我第一次看到这题的时候第一反应是这不就是个计数题吗直接一个字典或者哈希表统计每个数字出现的次数最后遍历一遍找出次数为1的就行。这个思路完全没有错它能在O(n)时间内解决空间复杂度是O(n)。如果题目没有额外限制这绝对是最容易想到、也最不容易写错的方案。但问题就出在不使用额外空间这个要求上。一旦空间复杂度被限制到O(1)哈希表方案就作废了这个时候就需要换个角度重新审视整个问题。很多新手卡在这里不是不会用哈希表而是被不用额外空间这句话限制住了思维不知道还能用什么办法。1.2 为什么哈希表不是最优解哈希表的思路本质上是记录每个数字出现的次数这是最直观的思维模式。但仔细想想题目给了一个非常强的条件除了目标数字之外其他数字都出现且仅出现两次。这个两次不是随便给的它背后藏着数学性质而这个性质哈希表完全没有利用上。如果你只是无脑计数等于是用一个通用工具解决一个特殊问题。通用工具的好处是适用范围广坏处是在特定场景下效率不是最优。比如在数据量极大的情况下哈希表会占用大量内存在分布式场景下哈希表也没法轻松扩展到多机并行。而位运算解法一旦想通了代码就三五行时间O(n)、空间O(1)这才是针对其他数字都出现两次这个特殊条件量身定做的方案。所以说解这道题的关键不在于会不会用哈希表而在于能不能发现成对数字之间可以互相抵消这个规律。一旦抓住这个规律整个问题的复杂度直接降一个维度。1.3 核心思路成对抵消的思想抵消这个词是我在跟别人讲这道题时最喜欢用的一个词。想象你手上有一堆卡片每个数字出现两次只有一张卡片只出现一次。你要找出那张落单的卡片。如果有个魔法能让两张相同的卡片碰在一起就自动消失那把所有卡片过一遍最后剩下的自然就是那张落单的卡片。位运算里的异或XOR恰好就是这种魔法两个相同的数字异或的结果是0任何数字和0异或的结果还是它本身。于是你把整个数组从头到尾异或一遍所有成对出现的数字都互相抵消变成0最后剩下的就是那个只出现一次的数字。这个思路的精髓在于它不需要记忆数字出现的次数也不需要额外空间去记录状态靠的是运算本身的数学性质。这正是位运算在算法题里的独特魅力——很多看似复杂的计数问题一旦用上异或、与、或、非这些基础运算代码会简洁到不可思议。2. 异或运算原理与代码实现2.1 异或运算的三个关键性质要彻底理解这道题的最优解必须先吃透异或运算的规则。异或的符号是^它的运算规则是两个位相同则为0不同则为1。比如5 ^ 3二进制分别是101和011逐位异或得到110也就是6。在算法里异或有三个非常关键的性质务必背到滚瓜烂熟归零律a ^ a 0任何数异或它自己结果都是0。恒等律a ^ 0 a任何数异或0结果还是它本身。交换律和结合律a ^ b ^ c a ^ c ^ b b ^ a ^ c异或的顺序不影响最终结果。这三个性质组合起来就构成了本次解法的基础。因为异或满足交换律和结合律所以数组中所有数字无论以什么顺序异或最终结果都一样。于是你可以把每个出现两次的数字先内部抵消掉剩下的就是答案。让我举一个具体的例子。数组是[4, 1, 2, 1, 2]把整个数组异或一遍就是4 ^ 1 ^ 2 ^ 1 ^ 2利用交换律重新排列4 ^ (1 ^ 1) ^ (2 ^ 2)因为1 ^ 1 02 ^ 2 0所以原式变成4 ^ 0 ^ 0 4最终结果就是4也就是数组中只出现一次的那个数。整个计算过程不需要额外空间不需要排序只需要一次遍历。2.2 完整代码与逐步拆解用Python写这个解法代码简洁到几乎不需要注释def singleNumber(nums): result 0 for num in nums: result ^ num return result别看这个代码短每一步都有讲究。result初始化为0利用的就是任何数异或0等于它本身这个性质。遍历数组时每遇到一个数字就将当前的result和它做异或。遇到成对的数字时result会先变成某个值再遇到它的配对时又变回原来的状态遇到落单的数字时它会一直保留在result里因为后面再也没有另一个它来抵消了。如果换成Java写法几乎一样class Solution { public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; } }这里有一个细节值得注意在Java里int是32位有符号整数异或运算按二进制逐位进行不会出现溢出的问题。在Python里整数是任意精度也不存在溢出问题。所以这个解法在主流语言里都能直接跑通不需要特殊处理数据类型。2.3 为什么这个解法一定正确要证明这个解法正确其实只需要做一个简单的数学归纳。假设数组里有n个数字其中n-1个数字都出现两次剩下1个数字只出现一次。把所有数字异或起来根据交换律和结合律先把成对的数字分到一组它们异或的结果是0再把所有0异或在一起结果还是0最后剩下的那个数字和0异或等于它本身。这个过程没有用到任何猜测或假设每一步都是确定的数学推导。所以不论数组里数字的顺序如何、数值大小如何、正负如何只要满足其余元素均出现两次这个条件答案一定正确。这也是为什么我特别推崇这个解法它不仅仅是一段能通过的代码更是一个可以严格证明的数学结论。在面试中如果你能把上面的推导过程清晰讲出来面试官对你的逻辑能力会印象深刻这比单纯背代码要有效得多。3. 变体问题实战从出现两次到出现三次3.1 LeetCode 137只有一个数字出现一次其余出现三次面试官看完你用异或解决136题之后最常问的变体就是如果题目改成除了某个元素只出现一次其余每个元素均出现三次还能用异或解决吗答案是不能因为三个相同的数字异或的结果不是0而是它本身。比如5 ^ 5 ^ 5 5三个5异或完还是5这样抵消不了。所以异或这个工具在这里就失效了需要换一种位运算思路。这个变体对应LeetCode 137题核心思路变成了按位统计。对于数组中所有数字的某一位比如二进制的最低位统计这一位上1的个数然后对3取模。如果取模结果是0说明这一位上1的个数是3的倍数如果取模结果是1说明目标数字的这一位是1。这里面的“为什么”需要解释清楚。因为数组中除了目标数字外其他数字都出现三次所以对任意一位来说所有非目标数字在这一位上贡献的1的个数一定是3的倍数每个数字贡献0或1三个同样的数字贡献0或3。目标数字贡献的1的个数要么是0、要么是1。所以统计总个数后对3取模余数就是目标数字在这一位的值。3.2 按位统计代码实现用Python实现这个思路def singleNumber(nums): result 0 for i in range(32): count 0 for num in nums: count (num i) 1 if count % 3 ! 0: result | (1 i) return result外层循环遍历32个二进制位内层循环统计所有数字在第i位上1的个数。(num i) 1的作用是取出数字num的第i位右移i位后和1做按位与运算得到0或1。如果count % 3不为0说明目标数字的这一位是1用按位或运算把它写进result里。这里最容易踩的坑是Python对负数的处理。上面这段代码在遇到负数时会有问题因为Python的整数是无限精度的负数的二进制表示在低位上和其他语言不同。如果你在LeetCode上跑这段代码会发现在某些测试用例上报错。解决办法是在返回前做一次判断如果result的最高位是1即它超过了32位有符号整数的正数范围就把它转换成对应的负数def singleNumber(nums): result 0 for i in range(32): count 0 for num in nums: count (num i) 1 if count % 3 ! 0: result | (1 i) return result if result 2**31 else result - 2**32这个处理可能让不少初学者困惑但它的原理其实不复杂。32位有符号整数的范围是[-2^31, 2^31 - 1]。如果按位统计出来的result大于等于2^31说明它的最高位第31位是1在补码表示下这是一个负数。result - 2^32就是把无符号视角的值转换回有符号的负数。3.3 如果有两个只出现一次的数字还有一个高频变体LeetCode 260数组中除了两个数字只出现一次其余数字都出现两次找出这两个数字。这个变体是136题的进阶版思路也有意思。先把所有数字异或一遍得到的结果是两个目标数字的异或值。因为这两个数字不同所以异或值不为0一定存在某一位是1。这个为1的位意味着这两个数字在这一位上一个为0、一个为1。接下来把这个数组分成两组以这一位为0、1作为划分标准。每组里都包含一个目标数字而其他成对的数字由于相同在某一位上一定相同所以它们会落在同一组里并且内部继续成对。两组分别做异或就能分别得到两个目标数字。写成代码就是这样def singleNumber(nums): xor_all 0 for num in nums: xor_all ^ num diff_bit xor_all (-xor_all) a, b 0, 0 for num in nums: if num diff_bit: a ^ num else: b ^ num return [a, b]这里有一个非常经典的位运算技巧xor_all (-xor_all)可以提取出xor_all二进制表示中最右侧那个1。在补码表示里-xor_all等于xor_all按位取反再加1。两者做按位与其他位全变成0只有最右侧的1保留下来。这个技巧在很多位运算题目里都会用到值得单独记下来。分组之后两个目标数字被分到不同组组里其他数字都是成对出现的所以每组内部做异或就只剩目标数字。整个过程同样是一次遍历加一次分组遍历时间复杂度O(n)空间O(1)。4. 通用解法与性能对比4.1 解决出现k次的通用方法刷完136、137、260三道题之后你会发现一个问题能不能有一个统一的解法直接解决除了一个数字出现一次其余数字都出现k次这个通用场景答案是有的而且思路就是137题按位统计的进一步推广。不管其余数字出现几次只要它们出现的次数相等对每个二进制位统计1的个数再对k取模余数就是目标数字在该位的值。def singleNumber(nums, k): result 0 for i in range(32): count 0 for num in nums: count (num i) 1 if count % k ! 0: result | (1 i) return result if result 2**31 else result - 2**32注意这里的k是任意正整数可以是2、3、5只要满足其他数字都出现k次的条件就行。这个通用解法可以帮你把一个专题的所有题目统一起来在面试时能体现很强的归纳总结能力。更进一步如果k比较大直接用计数器对每个位统计累加再取模时间复杂度是O(32n)仍然是线性。不过当k是2的幂时有更优雅的有限状态机解法也就是用数字电路里的状态转换来模拟模k计数器。这个做法的门槛稍微高一些大部分面试场景下不需要掌握那么深但了解一下无妨。4.2 不同解法的时间与空间对比为了让你对不同解法有更直观的认识我把常见的几种方案放到一张表里对比解法时间复杂度空间复杂度是否满足限制哈希表计数O(n)O(n)空间超限排序后相邻比较O(n log n)O(1)时间超限双层循环逐个统计O(n^2)O(1)时间超限异或位运算O(n)O(1)最优解从这个表里可以很清楚地看到为什么异或解法是这道题的标准答案。它的时间复杂度和空间复杂度同时达到最优没有任何一个维度是短板。更重要的是它的常数也很小因为异或运算在CPU层面是一条指令就完成的操作比哈希表需要计算哈希值、处理冲突要快得多。实际刷题时如果数据规模是10^5级别哈希表还能勉强应付但如果数据规模到10^7、10^8哈希表的内存占用就是灾难。位运算解法在这种极端情况下依然稳如泰山这也是它被大厂面试官偏爱的原因之一。4.3 从这道题延伸出去的位运算技巧这道题背后的位运算技巧其实在很多其他场景里都能复用到。我简单列举几个判断一个数是否是2的幂n 0 and (n (n - 1)) 0。统计一个数的二进制中有多少个1count n 1; n 1或者用n (n - 1)反复清零最低位的1。交换两个数而不使用临时变量a ^ b; b ^ a; a ^ b。提取最右侧的1n (-n)这在260题里已经用到过。这些技巧单独看不难但组合起来能解决很多看似复杂的位运算题目。我建议你刷题的时候不要只盯着AC而是把每个解法用到的位运算性质整理到笔记本上时间长了自然就形成条件反射了。5. 实际刷题中常踩的坑5.1 Python负数问题我在讲137题时已经提过一次Python负数问题但这里想再单独强调一下因为它真的很容易踩。在C和Java里int是固定32位的负数用补码表示位运算的结果符合直觉。但在Python里整数没有位数限制负数在内存中表示为无限长的1扩展如果要模拟32位整数的位运算结果必须自己处理符号位。最简单的处理方式是按32位统计完每一位之后如果result 2**31就减去2**32。这样得到的结果和C里int的补码表示是一致的。我在LeetCode上不少题解里都看到有人忽略这一点导致某些负数测试用例过不了这个细节一定要留意。5.2 异或结果别随手打印负数的二进制第二坑是关于异或结果的理解。当你把两个正数异或成一个看起来很大的数时不要先入为主觉得它就是正数。比如在260题里diff_bit是通过xor_all (-xor_all)提取出来的这个值是正数它只是用来分组的一个掩码不代表什么实际含义。真正理解位运算要习惯从二进制的角度去思考而不是盯着十进制数值纠结。5.3 注意题目变体里的边界条件最后一个常踩的坑是题目变体里的边界条件。比如有的变体会要求除了一个数字出现一次其余数字都出现奇数次这个条件就不满足上面的通用取模解法因为奇数次和偶数次的抵消规则完全不同。再比如LeetCode的某些变体允许数组为空这时候要提前处理空数组的情况否则直接访问nums[0]会报错。我在实际刷题时养成了一个习惯写代码前先看三遍题目确认出现几次是否有序是否包括负数数组是否可以为空这四个问题。这四个问题的答案不同解法可能完全不同。在面试里提前问清楚边界条件也是一种被认可的做法面试官通常会因为你的严谨而加分。就我个人经验而言处理位运算相关题目最重要的是先把二进制表示和补码规则吃透再用几个经典题目把异或、与、或的常用技巧练熟。像只出现一次的数字这类题目难度不大但延伸性极强非常适合用来检验自己对位运算的理解深度。如果你能把本文提到的136、137、260三道题都独立写出来并且能随口解释清楚每一步的运算原理那位运算这一关基本就稳了。