1. 先读懂“只出现一次的数字”到底考什么第一次刷到这道题的时候大多数人会觉得它简单但我后来发现真正能在面试里把这题答透的人并不多。题目本身不复杂给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现两次要求找出那个只出现了一次的元素。很多人看到“只出现一次的数字”这个关键词第一反应就是开个哈希表计数也确实能过。但题目如果要求线性时间复杂度并且不使用额外空间哈希表就立刻出局了。这一步筛选直接决定了这道题在面试题单里的地位。这道题能成为“每日一题”里的常客不是因为解法少而是因为几种常见解法的复杂度跨度非常大。你可以用O(n^2)暴力双层循环可以用O(n)空间换时间也可以最终落到O(n)时间、O(1)空间的位运算上。同一个题目能把“暴力解法—哈希解法—位运算解法”全部梳理清楚的人说明对复杂度分析、数据结构、位运算性质都有基本概念。适合谁来刷说实话覆盖范围很广。刚入门算法的人可以用它练循环和哈希表准备校招的人可以用它练“从暴力优化到最优”有几年经验的人也可以拿它当试金石看看自己对位运算的理解是背代码还是真的懂原理。它表面上是一道“easy”题实际上是一道很典型的“由简入深”的题目。我建议你先别着急看答案把自己代入面试场景试着在纸上把能想到的解法都写一遍再对照后面的内容。这样比直接看结论有效得多。2. 别急着写代码先罗列你能想到的解法2.1 暴力双层循环最直观也最不划算如果没有任何限制条件最朴素的想法是遍历每个元素再遍历一次数组数一下它出现了几次。一旦发现有哪个数字从头到尾只出现过一次就直接返回它。def singleNumber(nums): for i in range(len(nums)): found False for j in range(len(nums)): if i ! j and nums[i] nums[j]: found True break if not found: return nums[i]这个解法没有任何技巧遍历次数是n*n时间复杂度O(n^2)空间复杂度O(1)。放在小样本上没有问题但数组一旦上万性能会肉眼可见地变差。更重要的是这个解法在面试里没有任何区分度面试官不会满意。很多人在现场会先给出这个方案来“热身”这没问题。但如果你说完这个就停了面试官会觉得你停留在“能跑就行”的阶段而不是“能高效解决问题”的阶段。2.2 哈希表以空间换时间的常规思路比暴力更好想的是用哈希表。遍历数组时统计每个数字出现的次数最后再遍历一次哈希表找到出现次数为1的那个数。def singleNumber(nums): counter {} for num in nums: counter[num] counter.get(num, 0) 1 for num, cnt in counter.items(): if cnt 1: return num还有一个更巧妙的哈希表写法用一个集合遇到第一次出现的数字就加入遇到第二次出现的数字就移除。因为题目里除了目标数字之外其他数字都恰好出现两次所以最后集合里剩下的那个就是答案。def singleNumber(nums): seen set() for num in nums: if num in seen: seen.remove(num) else: seen.add(num) return seen.pop()这两种写法的时间复杂度都是O(n)但空间复杂度都是O(n)。如果题目额外要求“不使用额外空间”哈希表就会被直接否决。哪怕没有这个要求我也建议你在心里评估一下空间开销尤其是面试时主动说出“这个方案空间复杂度是O(n)”比等着面试官问要好得多。2.3 排序再找代码简单但时间复杂度上去了另一种常见思路是先把数组排序这样成对出现的数字会挨在一起。排序之后只需要每两个元素一组进行比较如果发现某一对不相等那前一个元素就是答案如果所有配对都相等那最后一个元素就是答案。def singleNumber(nums): nums.sort() i 0 while i len(nums) - 1: if nums[i] ! nums[i 1]: return nums[i] i 2 return nums[-1]排序法的时间复杂度取决于排序算法通常是O(n log n)空间复杂度看语言实现可能是O(log n)。要注意的是nums.sort()是原地排序会修改原数组。如果题目没说允许修改或者后续还需要用到原数组就需要先拷贝一份这又增加了额外空间。实际面试里排序法可以作为过渡方案提一嘴但不要作为最终答案。2.4 数学法用集合求和做差还有一个比较取巧的做法。既然其他数字都出现了两次那么去重后所有数字之和的两倍减去原数组所有数字之和剩下的就是那个只出现一次的数字。def singleNumber(nums): return 2 * sum(set(nums)) - sum(nums)思路很聪明代码很短但有两个问题第一set(nums)本身需要额外的O(n)空间第二在大整数场景下2 * sum(set(nums))可能非常大在某些语言里存在溢出的风险。Python的整数可以无限扩大倒还好但在C、Java里就要慎重。这道题的经典要求是“不使用额外空间”所以数学法通常也只是备选不是最优解。3. 位运算异或解法为什么代码只有一行3.1 异或运算的本质和三个性质如果所有数字里除了一个落单其他都成对出现那么最好的办法不是“记住谁出现过”而是“让成对的数字互相抵消”。能够天然做到这一点的是位运算里的异或符号是^。异或的规则很简单两个位相同结果为0两个位不同结果为1。aba ^ b000011101110基于这个真值表可以推出三个最重要的性质a ^ a 0自己和自己异或每一位都相同结果每一位都是0。a ^ 0 a和0异或每一位都保持不变。异或满足交换律和结合律a ^ b ^ c c ^ b ^ a先算谁后算谁不影响结果。你可以把异或理解成“找不同”两个人站在一起一模一样就抵消有不一样的地方才会留下痕迹。成对出现的数字在异或过程里全部清零最后剩下来的就是那个只出现了一次的数字。3.2 为什么一次遍历就能得到答案假设初始值是ans 0我们把数组里所有数字逐个和ans做异或。由于异或满足交换律和结合律所有成对的数字都会以x ^ x 0的形式抵消最后剩下的就是0 ^ target target。换句话说代码不需要判断当前数字之前出现过没有不需要计数不需要额外存储空间只需要从头到尾异或一遍。def singleNumber(nums): ans 0 for num in nums: ans ^ num return ans如果非要追求极简Python里可以用reduce写一行from functools import reduce from operator import xor def singleNumber(nums): return reduce(xor, nums, 0)循环版本的意图更清晰面试时优先推荐写循环不要一上来就写reduce。reduce虽然短但需要额外解释反而增加沟通成本。3.3 边界情况和“返回0”的迷惑性有一个细节容易被新手忽略如果数组只有一个元素比如[7]那么初始0 ^ 7直接得到7答案正确。如果数组是[0]返回值也是0。这时候看起来好像是程序“没找到”某个数而返回默认值实际上0就是那个只出现一次的元素只是恰好和初始值相同了。还有一种情况数组是[0, 0, 5]异或结果是5。要注意如果目标数字本身是0结果会是0这并不代表程序出错。只要题目保证“一定存在一个只出现一次的数字”返回0就是合法答案。负数也不用担心。Python的整数支持按位异或负数在底层以补码形式参与运算最终结果依然正确。比如[-1, -1, 2]0 ^ -1 -1再-1 ^ -1 0最后0 ^ 2 2结果没问题。4. 把一次异或过程亲手推一遍4.1 用经典用例做手工演算题目里最经典的例子是[4, 1, 2, 1, 2]因为其他数字都出现了两次4只出现一次结果应该是4。我们用ans 0开始一步步看步骤当前ans读取数字计算过程新的ans初始0无001040 ^ 442414 ^ 153525 ^ 274717 ^ 165626 ^ 24最终结果是4正确。只看数字看不出什么规律但如果换成二进制会清楚很多。4的二进制是01001是00012是0010。每一步0000 ^ 0100 01000100 ^ 0001 01010101 ^ 0010 01110111 ^ 0001 01100110 ^ 0010 0100你会发现中间结果一直在变化但最后又回到了0100也就是4。原因就是两个1和两个2在异或过程中互相抵消了。4.2 换一个遍历顺序结果也不变异或满足交换律和结合律所以数组顺序不会影响结果。我们把[4, 1, 2, 1, 2]重新排成[1, 1, 2, 2, 4]再走一遍初始00 ^ 1 11 ^ 1 00 ^ 2 22 ^ 2 00 ^ 4 4这样更直观两个1先抵消两个2再抵消最后只剩4。这也是为什么异或解法不需要关心“数字出现在数组的什么位置”只需要保证所有元素都被遍历到。4.3 自己验证时可以用“偶数次”视角如果题目把条件放宽成“只有一个数字出现奇数次其他数字都出现偶数次”异或解法依然成立。因为偶数个相同数字异或结果是0奇数个相同数字异或结果相当于这个数字本身。这道题里的“每个其他元素均出现两次”正好是最简单的偶数次场景。你可以随手拿几个数组测试[1]结果是1。[1, 2, 2]结果是1。[2, 1, 2]结果是1。[0, 0, 0, 0, 9]结果是9。最后一个例子里有4个0偶数个0异或后还是0最后0 ^ 9 9。理解了“偶数次抵消”这个视角后面做变体题会轻松很多。5. 面试时最容易被追问的四个变体5.1 如果其他数字都出现三次呢这是最常见的follow-up也就是“只出现一次的数字 II”。题目变成给定数组除了一个数字出现一次其他数字都出现三次找这个数字。异或不能直接解决因为三个相同数字异或的结果还是它自己x ^ x ^ x x没法抵消。标准解法是统计每一位上1出现的次数然后对3取模。出现三次的数字每一位贡献的1一定是3的倍数取模后为0唯一出现一次的数字留下模3余1的那些位。def singleNumber(nums): ans 0 for bit in range(32): count 0 for num in nums: count (num bit) 1 if count % 3 1: ans | (1 bit) if ans 2**31: ans - 2**32 return ans这段代码在Python里需要注意负数处理。如果你只刷接口题用哈希表也能过但“不使用额外空间”的约束下位计数法才是面试官想听到的答案。这个变体的核心思路是把成对的抵消思想从“整个数字异或”下沉到“每一位分别统计”。5.2 如果要求找两个只出现一次的数字呢这是另一个高频变体原题是“Single Number III”。思路分三步第一遍异或所有数字得到两个目标数字的异或结果xor_all x ^ y。因为x ! yxor_all至少有一个二进制位是1这个位上x和y不同。根据这个位把所有数字分成两组每组再分别异或就能得到x和y。取最低的1位可以用diff xor_all (-xor_all)这一步在Python里很常用。def singleNumber(nums): xor_all 0 for num in nums: xor_all ^ num diff xor_all (-xor_all) a 0 b 0 for num in nums: if num diff: a ^ num else: b ^ num return [a, b]这道题能拆出来说明你已经不是背解法而是真的理解了异或分组的意义。面试官经常会用这个变体来判断候选人是“记住了”还是“会了”。5.3 如果重复次数不是2但目标是“偶次抵消”呢有一种快速判断方法只要题目里“其他数字都出现偶数次”不管出现2次、4次还是6次异或解法都成立。因为从异或的角度看偶数个相同数字的异或结果都是0。这个点可以在面试时主动说出来它能体现出你抓住了问题本质而不是只背了一个公式。5.4 如果数组大到没法一次性装进内存呢哈希表需要保存每个数字的状态内存会随着数据规模线性增长。但异或解法只需要一个整数变量无论数组数量级是1万还是10亿额外空间占用都保持不变。这就是“常量空间”的意义。在实际的数据流场景里如果要求实时统计唯一落单的数并且其他数据都能满足“成对出现/偶数次出现”异或几乎是唯一可行的方案。它不需要回看历史数据也不用保存中间集合这种特性在流式处理里非常值钱。6. 实战经验与避坑清单6.1 面试时的回答顺序从暴力到最优我建议你在面试时不要直接甩出异或解法哪怕你早就看穿了答案。一个让面试官舒服的表达顺序是先说最直观的暴力法承认它时间复杂度高。再说哈希表指出时间O(n)但空间O(n)。最后说位运算解释异或的三个性质给出O(n)时间、O(1)空间的解法。每一步都要说清“上一个方案为什么不够好”。这不是卖关子而是让面试官看到你对复杂度的敏感度。实际面试中很多人一上来写哈希表也能过但只要面试官追问一句“能不能不用额外空间”就会卡住。提前按这个顺序组织语言能避免这种尴尬。6.2 这几个坑我踩过你也别再踩第一个坑是直接在原数组上排序。排序解法虽然代码短但如果题目环境不允许修改原数组或者后续逻辑依赖数组原顺序就会出错。最好先问一句“可以修改输入数组吗”第二个坑是忘记考虑长度为1的数组。很多人的异或代码是从某个默认值开始循环如果数组只有一个元素依然能正确返回。但如果你写的是“先取第一个元素然后从第二个开始循环”就要额外处理长度为1的情况否则数组越界。第三个坑是Python里用reduce写一行。不是不行而是面试时容易被人追问“这一行到底做了什么”。reduce适合表演不适合清晰沟通。我建议先用四行循环把逻辑讲透如果面试官对Python有偏好再补充一句“也可以用reduce完成”。问题场景错误做法正确做法数组只有一个元素从第二个元素开始循环设ans0遍历全部元素或者单独处理目标数字是0以为结果0是异常0就是合法答案无需特殊处理输入数组包含负数担心异或结果出错Python补码运算不影响结果排序解法直接原地排序确认是否允许修改原数组reduce写法为了简洁直接用优先可读的循环版本6.3 把这道题变成自己的“位运算模板”刷题最忌讳的是“这道题我见过代码我背下来了”。真正有效的做法是把一道题抽象成一个可复用的思考模板。“只出现一次的数字”可以抽象成一句话某个元素出现一次其他元素出现次数满足某种规律要想办法让成批的元素抵消留下目标。这种“抵消”思路不仅能用在异或上还能用在哈希表的add/remove写法上也能用在位计数取模上。你每做一道题都应该想想它的解法还能用在什么场景。比如异或的diff xor_all (-xor_all)取最低位技巧在树状数组、状态压缩题里也经常出现。一道简单题背后的工具可能比你想象的更值钱。7. 写在最后一次异或带来的提醒我自己第一次看到异或解法时第一反应是“怎么可能这么短”。后来在面试别人时我发现能清楚讲出“a^a0、a^0a、交换结合律”的候选人并不多大多数人只是背了个结果。所以我建议你刷完这道题后亲手在纸上推一遍二进制的异或过程再试着把题目改成“其他数字出现三次”和“找两个只出现一次的数字”。等你能把这些变体都理清楚这道“每日一题”的价值才算是真正榨干了。最后再分享一个小技巧每次刷到这种看似简单的题都先问自己一句“如果禁用我最先想到的数据结构我还能怎么做”很多高分解法都是被这个追问逼出来的。