这个题目其实是力扣上“只出现一次的数字”系列的第三题老粉丝应该一眼就认出来了。前面两道题一个用异或就能秒杀一个需要位运算加状态机到了第三题难度开始上去整个数组里有两个只出现一次的数字剩下全部成对出现让你把那两个“孤儿”找出来。标题里那个“(5)”大概率是题号或者系列的某种标记这不重要重要的是这题是理解位运算分组思想最好的一道模板题。我前后刷过不下五遍这题每次带新人讲位运算都会拿它当压轴案例今天把整个思路、推导、代码、坑全拆开了讲保证你看完不只是会AC而是真正理解为什么异或能把两个数拆开。1. 题目场景与系列定位1.1 问题描述还原先还原一下题目本来的样子。给你一个整数数组nums除了两个数字只出现一次之外其余每个数字都恰好出现两次。注意是恰好出现两次不是一次也不是三次。要求你用线性时间复杂度解决并且最好只使用常量级别的额外空间。举个例子输入: nums [1, 2, 1, 3, 2, 5] 输出: [3, 5] // 顺序不限在这个例子里1和2都出现了两次3和5只出现一次。题目要求返回这两个数字顺序不做要求。这个题的限制很明显O(n)时间、O(1)空间。这就排除掉了哈希表——统计频率很好用但空间显然是O(n)不合格。也排除掉了排序——排序的时间复杂度一般是O(n log n)不合格。剩下的路其实很窄要么用位运算要么用一些花哨的原地算法但位运算永远是这个系列的最优解。1.2 三部曲对比从一道题看思路进化先回忆一下这个系列的前两道题这样你才能体会第三题在思路上到底递进了什么。第一题Single Number整个数组只有一个数字出现一次其他都出现两次。解法就一行逻辑把全部数字异或起来成对出现的自动抵消成0剩下的那个就是答案。核心依据是异或的自反性a ^ a 0a ^ 0 a。第二题Single Number II一个数字出现一次其他数字出现三次。异或就不够用了因为a ^ a ^ a a三重的抵消不了。经典解法是统计每一位上1出现的次数对3取模最后拼出那个唯一的数字。也可以用数字电路里的状态机思路来压缩空间。第三题也就是今天这个Single Number III其他数字出现两次但有两个落单的。这题的难点在于如果只做一次全员异或我们得到的是两个目标数字的异或值x ^ y这不是答案本身。必须想办法把这两个数字从混合信号里分离出来。所以你会发现整个系列其实是在教一件事怎么用位运算去筛选、分离、还原数据。第一题是“异或直接给你答案”第二题是“逐位统计并用模运算恢复”第三题是“先混合再分组再分离”。每一题的解法都是上一题的延伸不是凭空蹦出来的新方法。2. 位运算为什么能解决这个问题2.1 异或运算的三条铁律要彻底看懂这题先把异或的三条性质焊死在脑子里交换律和结合律异或的顺序不影响结果a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)。这意味着我们可以把数组里的数字任意挑出来异或结果都一样。自反性a ^ a 0一个数和自己异或每一位都相同相同位异或得0。恒等性a ^ 0 a任何数和0异或不变。这三条性质加起来给了我们一个强大的工具成对出现的元素会被清零单独存在的元素会保留下来。这就像在一堆成对袜子中找出落单那只。你不需要知道每只袜子长什么样只要把所有袜子拿在一起做一次“成对抵消”的操作最后剩下的就是那只孤品。2.2 为什么第一遍全员异或不够我们先尝试第一遍异或xor_all 0 for num in nums: xor_all ^ num因为其他数字都成对出现所以这一遍之后xor_all其实是x ^ y也就是那两个只出现一次的数字的异或结果。举个例子nums [1, 2, 1, 3, 2, 5]全员异或的过程就是1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5 0 ^ 0 ^ 3 ^ 5 3 ^ 5 6 // 二进制是 110注意6既不是3也不是5它是3和5的异或结果混合了两个数的信息。问题就变成了如何从x ^ y这个结果里把x和y分别还原出来。这里需要停一下想清楚一件事如果x y那x ^ y 0说明不存在两个不同的落单数字所以题目保证x ! y。这意味着x ^ y的结果一定不为0它的二进制表示里至少有一位是1。这一位对应着x和y在某一个比特位上的差异——一个在那一位上是0另一个在那一位上是1。这个观察是整个分离思路的基石。2.3 从“混合”到“分离”的关键一跃有了x ^ y不为0的保证我们可以选取某个特定的位作为分组依据。怎么选最常见的做法是取最右侧的那个1也就是lowbit。这样选择的好处有二一是它一定是x和y的差异位二是这个位是1的那些数字自成一派。我们把这个位叫作分组位。现在重新扫描一遍数组对每个数字检查它在这一位上是不是1。如果是1放进A组如果是0放进B组。因为其他成对出现的数字在这一位上的表现是相同的——它们是同一个数字二进制位当然一致——所以它们会被分到同一组进而在组内异或时互相抵消。而x和y必然因为它们在这一位上的差异被分到不同的组。这样一来每个组的异或结果就分别是x和y。这件事的巧妙之处在于分组的同时原有的配对关系并没有被破坏。你可以想象成把所有数字按“第k位是0还是1”分成两堆虽然你并不知道目标数字具体是谁但你知道它们一定散布在两堆里而且每堆里除了其中一个目标数字外剩下的全是成对出现的数字。清理掉成对的剩下就是目标。3. 核心思路解构3.1 第一遍扫描拿到差异位前面说过第一遍异或拿到xor_all x ^ y。这之后我们需要从xor_all里提取一个比特位用来做第二遍扫描的分组依据。最直观的做法是从最低位开始一位一位地检查找到第一个为1的位。用代码表示diff xor_all -xor_all这一行代码是整个算法里最精妙、也最容易让初学者困惑的部分。在Python里负数是用补码表示的-xor_all等价于对xor_all取反加1。一个数和它的负数做按位与得到的结果恰好是这个数最低位的1以及后面那些0。比如xor_all 6二进制是110-6的二进制补码是010考虑三位的话是010实际机器位数更多但低位一致110 010 010也就是2。这正是6的最低位1所在的位置。这个操作叫lowbit在树状数组、状态压缩DP里也经常遇到。它的本质是提取一个数的二进制表示中最低位的那个1。这里选最低位1而不是选其他位置的1纯粹是因为最容易计算。你也可以用循环找到任意一个1但diff -diff一行就能搞定效率最高也最优雅。3.2 第二遍扫描按分组位分流拿到diff之后它现在的二进制形式是...0010这样只有分组位那个位置是1其他位置都是0。我们用num diff来判断一个数字的分组num diff ! 0说明这个数字在分组位上也是1和y同组。num diff 0说明这个数字在分组位上是0和x同组。这里有一个细节值得注意判断条件是“这一位是否为1”而不是“与diff相等”。因为diff是一个只有一个1的特殊值判断num diff是否是0就是在判断num的这一位是否是1。有些同学会写成num diff diff这也能工作因为结果要么是0要么是diff本身但直接用! 0更直观也能避免一些类型上的歧义。分好组之后分别对两组做全员异或。因为成对的数字都被分到了同一组并互相抵消A组的异或结果就是其中一个目标数字B组的异或结果就是另一个。3.3 手推例子不要怕手动模拟别光看理论我们手动推一遍之前的例子。nums [1, 2, 1, 3, 2, 5] xor_all 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 6 diff 6 -6 2 // 二进制 010现在第二遍扫描1 2 0 - B组 2 2 2 - A组 1 2 0 - B组 3 2 2 - A组 2 2 2 - A组 5 2 0 - B组B组1 ^ 1 ^ 5 5A组2 ^ 3 ^ 2 3两组的结果分别是5和3正好就是答案。注意一个有意思的现象B组里成对的是1A组里成对的是2。原本成对的数字没有“两边各一个”因为它们完全相同在分组位上的取值必然相同所以不可能被分到不同组。这就确保了每组里除了目标数字外剩下的元素都出现偶数次可以被干净地抵消。4. 完整实现与复杂度分析4.1 代码模板多语言对照把上面的思路写成代码非常短。我先给出C版本vectorint singleNumber(vectorint nums) { int xor_all 0; for (int num : nums) { xor_all ^ num; } int diff xor_all -xor_all; int group_a 0, group_b 0; for (int num : nums) { if (num diff) { group_a ^ num; } else { group_b ^ num; } } return {group_a, group_b}; }Python版本def singleNumber(nums): xor_all 0 for num in nums: xor_all ^ num diff xor_all -xor_all group_a 0 group_b 0 for num in nums: if num diff: group_a ^ num else: group_b ^ num return [group_a, group_b]Java版本public int[] singleNumber(int[] nums) { int xorAll 0; for (int num : nums) { xorAll ^ num; } int diff xorAll -xorAll; int groupA 0; int groupB 0; for (int num : nums) { if ((num diff) ! 0) { groupA ^ num; } else { groupB ^ num; } } return new int[]{groupA, groupB}; }三个语言的实现几乎一模一样因为位运算是语言无关的底层操作。需要注意Java里优先级低于!所以要加括号Python和C里的优先级也需要注意但上面写的判空写法不会出问题。4.2 复杂度分析时间复杂度扫描了两遍数组每遍是O(n)所以总体是O(n)。这个n是数组长度。空间复杂度只用了几个整数变量没有申请额外数组或哈希表所以是O(1)。这个复杂度是题目明确要求的也是位运算解法最吸引人的地方。你可能觉得这个方案很玄但它在实际面试中几乎是标准答案。面试官看到你能写出这个解法就知道你不仅掌握了位运算的基本性质还能灵活运用“分组抵消”这种进阶思路。4.3 返回值顺序问题题目说输出顺序不限但有些版本的题目会要求升序返回。如果有这个要求就在返回值后面加个排序判断if group_a group_b: group_a, group_b group_b, group_a如果题目没有要求顺序这一步可以省略。不过养成排序习惯也不坏因为有的现场面试官会不看题目描述直接让你“输出这两个数”这时候你按升序给观感更好。5. 常见问题与踩坑记录5.1 为什么差值的lowbit一定存在有同学会问如果数组里所有数字都成对那xor_all就是0lowbit取不出来怎么办答案是这种情况不可能发生。题目保证有两个只出现一次且不同的数字所以x ^ y至少有一位是1。如果x y那只有一个落单的数字不属于这个题目的范围。换句话说xor_all 0这个分支不需要处理如果你真的遇到了说明你的测试用例不符合题目约束。5.2 分组时要不要对0单独处理不需要。0与任何数异或都等于那个数本身所以即使某个数字是0它参与分组也不影响异或结果。你只需要根据分组位对它做区分它在哪一组都没问题。不过这里有一个隐藏的考点如果目标数字之一是0比如数组是[0, 1, 2, 1, 2, 3]那么xor_all 0 ^ 1 ^ 2 ^ 1 ^ 2 ^ 3 3lowbit是1第二遍分组时0会被分到B组B组异或结果是0 ^ 1 ^ 1 0也没问题。所以不需要特殊处理0。5.3 负数的lowbit计算可能会踩坑Python和Java里负数用补码表示diff xor_all -xor_all对正数和负数都成立。比如xor_all -6它的二进制补码低三位是010-(-6)是6-6 6的结果是2依然正确。所以这个公式对任意非零整数都有效。但在C里有符号整数的位操作在不同编译器下的行为基本一致因为补码已经是工业标准。不过如果你用的是无符号整数取反操作会有完全不同的语义这里建议保持用有符号整数做异或和lowbit避免无符号数的隐式转换把结果搞乱。5.4 不要写成xor_all xor_all - 1提取最低位1常见的有两种写法x -x和x (~x 1)。后者虽然也行但写起来麻烦。有些初学者会误写成x (x - 1)这个操作实际上是清零最低位的1不是提取最低位的1差之毫厘谬以千里。x (x - 1)在统计二进制中1的个数时常用别记混了。5.5 第二遍扫描时不能中途改变分组依据有个很隐蔽的坑有些同学在第一遍异或之后想省变量直接把xor_all拿来当分组依据遍历时边分组边异或。但要注意不要在第二遍扫描过程中修改xor_all或者diff。因为分组位一旦确定就必须用同一个位去判断所有数字中途改掉的话后面的分组就全乱了。# 错误示范第二遍扫描中修改了diff for num in nums: if num diff: group_a ^ num diff diff 1 # 千万不要这么做这在实际中很少见但我在代码审查时见过有人为了“优化”而写出这种逻辑结果就是分组错乱答案完全不对。5.6 数组中数字很大时不要用位运算以外的花招如果数字范围很大比如达到2^31 - 1用哈希表没问题但空间超了。用排序思路在时间上超了。位运算没有任何溢出问题因为它本质就是逐比特计算。唯一需要留意的是Java的int只有32位如果你的测试数据超过这个范围那就需要用long。但力扣这类题的数据范围一般都在int内不用太担心。6. 延伸思考这套思路还能用在哪6.1 从两个落单数字扩展到多个Single Number III的思路其实不仅仅是解决这一个题目。它背后是“分组异或”这个范式凡是要在成对出现的数组里找几个特殊元素都可以往这个方向想。我之前在一个带新人的项目里就出过一道变体有三个数字只出现一次其他都出现两次问怎么找这三个数字。解法是先用某种规则把问题拆成“一个”和“两个”的组合再用今天的思路递归求解。原理一样只是分组位的选取变得更复杂。6.2 lowbit在树状数组中的应用diff x -x这个操作在树状数组Binary Indexed Tree里是核心操作叫lowbit。树状数组的更新和查询都要依赖它来跳转索引。如果这题学完你还想做点巩固可以顺手把树状数组的基本操作写一遍你会发现同样的位运算技巧在数据结构里会反复出现。6.3 其他位运算技巧配套使用另一个常见的配合是x (x - 1)用来清零最低位的1。这个技巧经常和lowbit一起出现在算法题里比如统计一个数的二进制表示中有多少个1count 0 while x: x (x - 1) count 1把这两个操作放一起记x -x提取最低位1x (x - 1)清除最低位1。一个取一个消互为补充。刷题久了你会发现位运算题的高频考点就这么几个操作来回组合。7. 个人实操体会这道题我反复讲了很多遍每次带新人都能发现几个共通的疑惑点。最典型的就是不理解为什么要选lowbit而不是选最高位或者中间任意一位。其实随便选一位都行只要那一位在x ^ y里是1就行lowbit只是因为代码简洁、运行快才成为默认选择。如果真的把代码改成“从高位往低位找第一个1”效果完全一样只是代码稍微长一点。还有一点我想特别强调面试或者笔试的时候代码写出来还不够一定要把“为什么能分到不同组”这个问题用嘴讲清楚。我见过不少候选人代码默写对了但被问到“如果两个目标数字在分组位上都相同怎么办”时卡住了——答案是它们不可能相同因为分组位就是从它们异或结果里挑出来的差异位既然x ^ y在这一位是1就说明它们在这一位必然不同。这个逻辑闭环是整个算法成立的前提你在任何场合使用这个方法都要随时能讲明白这一步。另外如果你是在本地IDE里调试建议把中间变量打印出来看一遍尤其是xor_all和diff。手动心算一遍例子的二进制形态比直接跑通代码更能加深印象。我第一次彻底理解这个题就是拿笔在草稿纸上画了一遍二进制画完之后再也没忘过。最后说句题外话。很多人觉得位运算晦涩平时业务开发里用不上就不愿意花时间学。但位运算恰恰是那种“平时用不到、用到就是关键优化”的知识很多高性能代码、嵌入式开发、图形学、网络协议栈里都有它的身影。而且刷算法题练的不仅是技巧本身更是一种“从限制条件出发倒推解法”的思维路径。这题的O(n)时间加O(1)空间直接把所有常规解法按死逼你走上位运算这条路等你走通了再遇到限制条件更苛刻的题目你的第一反应就会是“能不能用位运算做”这本身就是一种巨大的成长。