1. 问题引入与核心价值在算法面试和日常编程中有一类问题因其巧妙的解法和对位运算的深度考察而备受青睐这就是所谓的“单身狗问题”。这个名字很形象它通常指在一个数组中除了某个或某两个元素只出现一次外其余所有元素都恰好出现两次。我们的任务就是找出这个“落单”的数字。这类问题不仅是检验你对C位运算理解深度的绝佳试金石更是许多大厂面试中的高频考点比如经典的LeetCode 136题和260题。我第一次遇到这个问题时第一反应是排序后遍历或者用哈希表记录频次。这些方法固然可行但当你被面试官追问“时间复杂度O(n)空间复杂度O(1)的解法”时如果答不上来可能就与心仪的Offer失之交臂了。位运算解法正是那个“最优解”它优雅、高效且充满了计算机科学的智慧。理解它不仅能帮你解决这一系列问题更能让你对数据的二进制表示、异或操作的特性有颠覆性的认识。无论你是正在准备面试的求职者还是希望夯实C基础的开发者掌握“单身狗问题”的位运算解法都至关重要。2. 问题定义与基础解法剖析2.1 问题原型LeetCode 136. 只出现一次的数字这是该系列最基础也是最核心的问题。题目描述非常简单给定一个非空整数数组nums除了某个元素只出现一次外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现一个时间复杂度为 O(n) 且仅使用 O(1) 额外空间的算法。示例 1输入nums [2,2,1] 输出1示例 2输入nums [4,1,2,1,2] 输出4示例 3输入nums [1] 输出12.1.1 哈希表法空间换时间最直观的思路是使用一个哈希表在C中通常是std::unordered_map来记录每个数字出现的次数。遍历一次数组填充哈希表再遍历一次哈希表找出计数为1的元素。#include unordered_map #include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { unordered_mapint, int freq; for (int num : nums) { freq[num]; } for (auto [num, count] : freq) { if (count 1) { return num; } } return -1; // 根据题意不会走到这里 } };复杂度分析时间复杂度O(n)遍历数组和哈希表各一次。空间复杂度O(n)最坏情况下需要存储 n/2 1 个键值对。注意这个方法虽然简单易懂且时间复杂度达标但空间复杂度不符合题目“O(1)额外空间”的进阶要求。在面试中如果你只给出这个解法面试官很可能会追问更优解。2.1.2 数学求和法存在溢出风险另一种取巧的思路是利用集合std::set的特性。我们知道2 * (a b c) - (a a b b c) c。即所有不重复元素和的两倍减去原数组所有元素和就等于那个只出现一次的数。#include vector #include unordered_set using namespace std; class Solution { public: int singleNumber(vectorint nums) { unordered_setint numSet; long long sumSet 0, sumArray 0; // 使用long long防止大数溢出 for (int num : nums) { sumArray num; if (numSet.find(num) numSet.end()) { numSet.insert(num); sumSet num; } } return (int)(2 * sumSet - sumArray); } };复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(n)用于存储不重复元素的集合。实操心得这个方法在理论上很有趣但在实践中问题很大。首先它需要额外的集合存储空间复杂度不是O(1)。其次整数溢出是致命伤。即使使用long long如果输入数组极大或元素值极大依然有溢出风险。因此不推荐在面试或工程中使用此方法它更像一个思维练习。2.2 核心武器位运算与异或XOR的魔力要达成O(n)时间和O(1)空间我们必须请出位运算中的王牌——异或XOR符号为^。在深入解法前必须彻底理解它的四个核心性质归零律a ^ a 0。任何数与自身异或结果为0。恒等律a ^ 0 a。任何数与0异或结果为其本身。交换律a ^ b b ^ a。异或操作满足交换律。结合律(a ^ b) ^ c a ^ (b ^ c)。异或操作满足结合律。基于以上性质我们可以推导出一个至关重要的结论对于一系列数字进行异或操作出现偶数次的数字会两两抵消为0最终结果就是那个出现奇数次的数字。让我们用示例[4, 1, 2, 1, 2]来演算初始结果 result 0 result ^ 4 - 0 ^ 4 4 result ^ 1 - 4 ^ 1 5 (二进制 0100 ^ 0001 0101) result ^ 2 - 5 ^ 2 7 (二进制 0101 ^ 0010 0111) result ^ 1 - 7 ^ 1 6 (二进制 0111 ^ 0001 0110) // 第一个1被“抵消”了 result ^ 2 - 6 ^ 2 4 (二进制 0110 ^ 0010 0100) // 第一个2被“抵消”了 最终结果 result 4可以看到成对出现的1和2在异或过程中相互抵消最终只剩下孤零零的4。2.2.1 位运算标准解法理解了原理代码就异常简洁#include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; // 等价于 result result ^ num; } return result; } };复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(1)只使用了一个额外变量result。这就是该问题的终极答案优雅而强大。在面试中你应该首先阐述哈希表法等常规思路然后引出位运算解法并清晰解释异或的四个性质及其如何应用于此场景这能充分展示你的思维深度。3. 问题变种与进阶挑战掌握了基础问题后面试官不会就此罢休。他们会通过变种问题来考察你是否真正理解了位运算的本质以及举一反三的能力。3.1 变种一LeetCode 137. 只出现一次的数字 II题目升级给定一个整数数组nums除某个元素仅出现一次外其余每个元素都恰出现三次。请你找出并返回那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。示例输入nums [2,2,3,2] 输出3此时简单的异或失效了因为a ^ a ^ a a无法将出现三次的数抵消。我们需要更通用的思路按位统计。3.1.1 思路解析模拟三进制既然每个数字出现三次那么如果我们统计所有数字在每一位二进制位上“1”出现的总次数这个次数对3取模余数就是只出现一次的数字在该位上的值0或1。以数组[2,2,3,2]为例假设为4位整数数字2的二进制0010数字3的二进制0011统计每位1的个数第0位最低位2(0), 2(0), 3(1), 2(0) - 总和1 - 1 % 3 1第1位2(1), 2(1), 3(1), 2(1) - 总和4 - 4 % 3 1第2位全是0 - 总和0 - 0 % 3 0第3位全是0 - 总和0 - 0 % 3 0得到的二进制0011就是数字3。3.1.2 通用位计数解法我们可以用一个长度为32对于32位整数的数组来统计每一位上1的个数。#include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { int result 0; // 遍历整数的每一个位 for (int i 0; i 32; i) { int bitSum 0; // 遍历数组中的每个数统计第i位为1的个数 for (int num : nums) { // 将num右移i位后与1进行与操作得到第i位的值0或1 bitSum ((num i) 1); } // 如果该位的总和模3不为0说明只出现一次的数在这一位是1 if (bitSum % 3 ! 0) { // 使用或操作|将result的第i位置为1 result | (1 i); } } return result; } };复杂度分析时间复杂度O(32 * n) ≈ O(n)常数项较大但仍是线性。空间复杂度O(1)只使用了固定大小的额外变量。3.1.3 优化解法数字电路设计有限状态自动机上述解法需要遍历32次能否只遍历一次数组就得到结果可以但这需要一点数字电路的知识。我们可以用两个位twos和ones来表示当前位1出现次数的状态对3取模状态00表示出现0次。状态01表示出现1次。状态10表示出现2次。状态11本应表示出现3次但3取模后为0所以自动回到00。我们需要根据当前输入num的每一位设计状态转移方程。推导过程略复杂但最终代码非常精妙class Solution { public: int singleNumber(vectorint nums) { int ones 0, twos 0; for (int num : nums) { // ones num 得到的是“在ones为1且num当前位也为1”的位这些位将进入twos状态01-10 // ~twos 确保了当状态达到10出现两次时不会再接收新的1变成11。 ones (ones ^ num) ~twos; // twos num 得到“在twos为1且num当前位也为1”的位这些位表示出现了三次应清零 ~ones // ones num 是上一步计算出的新ones其中来自状态01-10的部分应转移到twos。 twos (twos ^ num) ~ones; } // 最终出现一次的数存储在ones中状态01出现两次的数存储在twos中状态10 return ones; } };这个解法理解起来有门槛但它是面试中的加分项体现了你对问题本质的深刻理解。如果现场推导不出来可以阐述思路“我们可以用两个比特位模拟状态机只遍历一次”。3.2 变种二LeetCode 260. 只出现一次的数字 III这是“单身狗问题”的另一个经典变种给定一个整数数组nums其中恰好有两个元素只出现一次其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。要求时间复杂度O(n)空间复杂度O(1)。示例输入nums [1,2,1,3,2,5] 输出[3,5] 或 [5,3]3.2.1 思路解析分组异或如果直接对整个数组异或得到的结果xor_all将是两个目标数a和b的异或值即xor_all a ^ b且xor_all必然不为0因为a不等于b。xor_all不为0意味着在二进制表示中至少有一位是1。假设第k位是1那么a和b在第k位上的值一定不同一个为0一个为1。这正是我们将两个数分到不同组的关键。步骤对数组所有元素进行异或得到xor_all a ^ b。找到xor_all中任意一个为1的位通常找最低位的1可以通过diff xor_all -xor_all快速得到这个技巧利用了补码的特性。根据这个位是否为1将原数组分成两组。由于相同的数在该位上的值相同所以成对的数一定会被分到同一组。而a和b因为该位值不同会被分到不同的组。分别对两个组进行异或操作问题退化为LeetCode 136得到的结果就是a和b。3.2.2 代码实现#include vector using namespace std; class Solution { public: vectorint singleNumber(vectorint nums) { // 第一步得到两个单身狗的异或值 long long xor_all 0; // 使用long long防止溢出 for (int num : nums) { xor_all ^ num; } // 第二步找到xor_all中最低位的1分组依据 // 技巧diff xor_all -xor_all // -xor_all 是 xor_all 的补码按位与后得到最低位的1 long long diff xor_all (-xor_all); // 第三步分组异或 int a 0, b 0; for (int num : nums) { if ((num diff) ! 0) { // 如果num在diff位上是1 a ^ num; } else { // 如果num在diff位上是0 b ^ num; } } return {a, b}; } };复杂度分析时间复杂度O(n)两次遍历数组。空间复杂度O(1)使用了固定数量的变量。注意事项这里使用long long是为了处理-xor_all可能对INT_MIN取负导致的溢出问题虽然LeetCode用例通常不会触发。更严谨的写法是int diff xor_all INT_MIN ? xor_all : xor_all (-xor_all);。理解分组依据是核心代码中的diff技巧需要掌握。4. 实战演练与深度扩展理解了原理和变种我们还需要在实战中巩固并思考更广泛的扩展场景。4.1 综合编码实践与测试让我们编写一个完整的程序测试上述所有解法#include iostream #include vector #include unordered_map #include cassert using namespace std; // LeetCode 136 解法位运算 int singleNumber_136(vectorint nums) { int ans 0; for (int num : nums) ans ^ num; return ans; } // LeetCode 137 解法位计数 int singleNumber_137(vectorint nums) { int ans 0; for (int i 0; i 32; i) { int bitSum 0; for (int num : nums) { bitSum ((num i) 1); } if (bitSum % 3) { ans | (1 i); } } return ans; } // LeetCode 260 解法分组异或 vectorint singleNumber_260(vectorint nums) { long long xor_all 0; for (int num : nums) xor_all ^ num; long long diff xor_all (-xor_all); int a 0, b 0; for (int num : nums) { if (num diff) a ^ num; else b ^ num; } return {a, b}; } int main() { cout 测试 LeetCode 136 endl; vectorint test1 {4, 1, 2, 1, 2}; cout 输入: [4,1,2,1,2] endl; cout 输出: singleNumber_136(test1) (期望: 4) endl endl; cout 测试 LeetCode 137 endl; vectorint test2 {0,1,0,1,0,1,99}; cout 输入: [0,1,0,1,0,1,99] endl; cout 输出: singleNumber_137(test2) (期望: 99) endl endl; cout 测试 LeetCode 260 endl; vectorint test3 {1,2,1,3,2,5}; vectorint res singleNumber_260(test3); cout 输入: [1,2,1,3,2,5] endl; cout 输出: [ res[0] , res[1] ] (期望: [3,5] 或 [5,3]) endl; // 验证 assert(singleNumber_136(test1) 4); assert(singleNumber_137(test2) 99); assert((res vectorint{3,5}) || (res vectorint{5,3})); cout \n所有断言通过 endl; return 0; }4.2 扩展思考更一般化的问题如果问题变为“只有一个数字出现一次其余数字出现k次”呢我们可以将位计数法推广int singleNumber_K(vectorint nums, int k) { int result 0; // 假设是32位整数 for (int i 0; i 32; i) { int bitSum 0; for (int num : nums) { bitSum ((num i) 1); } if (bitSum % k ! 0) { // 对k取模 result | (1 i); } } return result; }对于“两个数字出现一次其余出现两次”LeetCode 260可以看作是k2的特例但需要更巧妙的分组。对于“一个数字出现一次其余出现三次”LeetCode 137就是k3。这个方法的时间复杂度是 O(32 * n)空间复杂度 O(1)是通用解法。4.3 边界条件与陷阱排查在实际编码和面试中需要特别注意以下问题整数溢出在求和法或涉及-INT_MIN的操作时如求diff必须考虑溢出。优先使用位运算解法可以避免绝大多数溢出问题。负数处理C/C中右移负数 () 是算术右移高位补符号位。在统计位1的个数时如果使用for (int i0; i32; i)并右移i位对于负数也能正确处理因为我们是按固定32位处理的。但如果用while (num)循环就会出错。diff位的选择在LeetCode 260中选择xor_all中任意一个为1的位都可以。选择最低位的1 (diff xor_all -xor_all) 是最常见的技巧因为它高效且易得。输入验证题目通常保证输入有效非空且满足条件。但在实际工程中应增加检查例如数组是否为空。5. 面试实战技巧与心得总结经过对“单身狗问题”系列的深度剖析最后分享一些从面试官和面试者角度总结的实战心得。5.1 面试回答策略由浅入深不要一上来就甩出位运算答案。先给出最直观的哈希表法分析其时间O(n)、空间O(n)的复杂度。然后指出面试官可能对空间有要求再引出位运算解法。这展示了你的思维过程。解释原理而非背诵代码在阐述异或解法时一定要把四条性质归零、恒等、交换、结合讲清楚并用一个小例子如[4,1,2,1,2]现场演算。证明你真正理解而不是背题。主动思考变种在解答完基础问题后可以主动说“这个问题有一个经典的变种如果其他数字出现三次或者有两个‘单身狗’解法会有所不同……” 这体现了你的知识迁移能力和主动性。讨论复杂度与权衡明确说出位运算解法的时间复杂度O(n)和空间复杂度O(1)。可以提一下哈希表法虽然空间复杂度高但在某些需要知道是哪些数字成对出现的场景下更有用显示你的工程思维。5.2 常见问题与排查记录在自己练习或面试白板编码时你可能会遇到以下问题问题LeetCode 260的代码返回的两个数字顺序不对排查题目明确说明可以按任意顺序返回。你的代码逻辑只要正确找出两个数即可顺序无关紧要。检查分组逻辑是否正确特别是if ((num diff) ! 0)这个条件确保分组一致。问题处理负数时位计数法结果错误排查确认你是在对固定32位进行循环 (for (int i0; i32; i))并且使用(num i) 1来取位。算术右移会保持符号位但与我们按位统计1的个数的目标不冲突。避免使用while (num)的循环。问题状态机解法LeetCode 137完全看不懂如何掌握建议如果时间紧迫掌握位计数通用解法即可它能解决所有“出现k次”的变种且易于理解和记忆。状态机解法可以作为加分项去理解但不必强求现场推导。可以说“我知道还有一种利用位运算状态机只遍历一次的方法其原理是……”5.3 核心要点回顾与个人体会回顾整个“单身狗”系列其核心思想万变不离其宗利用位运算的特性在二进制层面上对信息进行统计和抵消。基础问题出现两次异或的“归零律”和“结合律”是神兵利器直接抵消成对数字。变种一出现三次/多次思路升维从“整体抵消”变为“按位统计再模运算”。这是解决更一般化问题的通用钥匙。变种二两个单身狗核心技巧是“分组”。通过找到两个目标数不同的比特位巧妙地将它们分到两个组每个组内就退化为基础问题。我个人在学习和教学过程中最大的体会是这类问题最好的学习方法不是死记硬背代码而是亲手在纸上进行二进制演算。把一个简单的例子比如[4,1,2,1,2]把每个数字的二进制写出来一步一步做异或亲眼看到数字如何抵消。对于变种问题也亲自画一画每一位上1的个数如何累积、如何取模。这个过程能帮你建立起牢固的直觉。最后C的位操作符,|,^,~,,是实现这些算法的基石务必熟练掌握它们的优先级和运算规则。当你再遇到此类问题时希望你能自信地拿起位运算这把利器优雅地解决它。
C++位运算精解：从异或到状态机，攻克“单身狗”算法面试题
发布时间：2026/7/20 11:02:41
1. 问题引入与核心价值在算法面试和日常编程中有一类问题因其巧妙的解法和对位运算的深度考察而备受青睐这就是所谓的“单身狗问题”。这个名字很形象它通常指在一个数组中除了某个或某两个元素只出现一次外其余所有元素都恰好出现两次。我们的任务就是找出这个“落单”的数字。这类问题不仅是检验你对C位运算理解深度的绝佳试金石更是许多大厂面试中的高频考点比如经典的LeetCode 136题和260题。我第一次遇到这个问题时第一反应是排序后遍历或者用哈希表记录频次。这些方法固然可行但当你被面试官追问“时间复杂度O(n)空间复杂度O(1)的解法”时如果答不上来可能就与心仪的Offer失之交臂了。位运算解法正是那个“最优解”它优雅、高效且充满了计算机科学的智慧。理解它不仅能帮你解决这一系列问题更能让你对数据的二进制表示、异或操作的特性有颠覆性的认识。无论你是正在准备面试的求职者还是希望夯实C基础的开发者掌握“单身狗问题”的位运算解法都至关重要。2. 问题定义与基础解法剖析2.1 问题原型LeetCode 136. 只出现一次的数字这是该系列最基础也是最核心的问题。题目描述非常简单给定一个非空整数数组nums除了某个元素只出现一次外其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现一个时间复杂度为 O(n) 且仅使用 O(1) 额外空间的算法。示例 1输入nums [2,2,1] 输出1示例 2输入nums [4,1,2,1,2] 输出4示例 3输入nums [1] 输出12.1.1 哈希表法空间换时间最直观的思路是使用一个哈希表在C中通常是std::unordered_map来记录每个数字出现的次数。遍历一次数组填充哈希表再遍历一次哈希表找出计数为1的元素。#include unordered_map #include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { unordered_mapint, int freq; for (int num : nums) { freq[num]; } for (auto [num, count] : freq) { if (count 1) { return num; } } return -1; // 根据题意不会走到这里 } };复杂度分析时间复杂度O(n)遍历数组和哈希表各一次。空间复杂度O(n)最坏情况下需要存储 n/2 1 个键值对。注意这个方法虽然简单易懂且时间复杂度达标但空间复杂度不符合题目“O(1)额外空间”的进阶要求。在面试中如果你只给出这个解法面试官很可能会追问更优解。2.1.2 数学求和法存在溢出风险另一种取巧的思路是利用集合std::set的特性。我们知道2 * (a b c) - (a a b b c) c。即所有不重复元素和的两倍减去原数组所有元素和就等于那个只出现一次的数。#include vector #include unordered_set using namespace std; class Solution { public: int singleNumber(vectorint nums) { unordered_setint numSet; long long sumSet 0, sumArray 0; // 使用long long防止大数溢出 for (int num : nums) { sumArray num; if (numSet.find(num) numSet.end()) { numSet.insert(num); sumSet num; } } return (int)(2 * sumSet - sumArray); } };复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(n)用于存储不重复元素的集合。实操心得这个方法在理论上很有趣但在实践中问题很大。首先它需要额外的集合存储空间复杂度不是O(1)。其次整数溢出是致命伤。即使使用long long如果输入数组极大或元素值极大依然有溢出风险。因此不推荐在面试或工程中使用此方法它更像一个思维练习。2.2 核心武器位运算与异或XOR的魔力要达成O(n)时间和O(1)空间我们必须请出位运算中的王牌——异或XOR符号为^。在深入解法前必须彻底理解它的四个核心性质归零律a ^ a 0。任何数与自身异或结果为0。恒等律a ^ 0 a。任何数与0异或结果为其本身。交换律a ^ b b ^ a。异或操作满足交换律。结合律(a ^ b) ^ c a ^ (b ^ c)。异或操作满足结合律。基于以上性质我们可以推导出一个至关重要的结论对于一系列数字进行异或操作出现偶数次的数字会两两抵消为0最终结果就是那个出现奇数次的数字。让我们用示例[4, 1, 2, 1, 2]来演算初始结果 result 0 result ^ 4 - 0 ^ 4 4 result ^ 1 - 4 ^ 1 5 (二进制 0100 ^ 0001 0101) result ^ 2 - 5 ^ 2 7 (二进制 0101 ^ 0010 0111) result ^ 1 - 7 ^ 1 6 (二进制 0111 ^ 0001 0110) // 第一个1被“抵消”了 result ^ 2 - 6 ^ 2 4 (二进制 0110 ^ 0010 0100) // 第一个2被“抵消”了 最终结果 result 4可以看到成对出现的1和2在异或过程中相互抵消最终只剩下孤零零的4。2.2.1 位运算标准解法理解了原理代码就异常简洁#include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; // 等价于 result result ^ num; } return result; } };复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(1)只使用了一个额外变量result。这就是该问题的终极答案优雅而强大。在面试中你应该首先阐述哈希表法等常规思路然后引出位运算解法并清晰解释异或的四个性质及其如何应用于此场景这能充分展示你的思维深度。3. 问题变种与进阶挑战掌握了基础问题后面试官不会就此罢休。他们会通过变种问题来考察你是否真正理解了位运算的本质以及举一反三的能力。3.1 变种一LeetCode 137. 只出现一次的数字 II题目升级给定一个整数数组nums除某个元素仅出现一次外其余每个元素都恰出现三次。请你找出并返回那个只出现一次的元素。要求时间复杂度O(n)空间复杂度O(1)。示例输入nums [2,2,3,2] 输出3此时简单的异或失效了因为a ^ a ^ a a无法将出现三次的数抵消。我们需要更通用的思路按位统计。3.1.1 思路解析模拟三进制既然每个数字出现三次那么如果我们统计所有数字在每一位二进制位上“1”出现的总次数这个次数对3取模余数就是只出现一次的数字在该位上的值0或1。以数组[2,2,3,2]为例假设为4位整数数字2的二进制0010数字3的二进制0011统计每位1的个数第0位最低位2(0), 2(0), 3(1), 2(0) - 总和1 - 1 % 3 1第1位2(1), 2(1), 3(1), 2(1) - 总和4 - 4 % 3 1第2位全是0 - 总和0 - 0 % 3 0第3位全是0 - 总和0 - 0 % 3 0得到的二进制0011就是数字3。3.1.2 通用位计数解法我们可以用一个长度为32对于32位整数的数组来统计每一位上1的个数。#include vector using namespace std; class Solution { public: int singleNumber(vectorint nums) { int result 0; // 遍历整数的每一个位 for (int i 0; i 32; i) { int bitSum 0; // 遍历数组中的每个数统计第i位为1的个数 for (int num : nums) { // 将num右移i位后与1进行与操作得到第i位的值0或1 bitSum ((num i) 1); } // 如果该位的总和模3不为0说明只出现一次的数在这一位是1 if (bitSum % 3 ! 0) { // 使用或操作|将result的第i位置为1 result | (1 i); } } return result; } };复杂度分析时间复杂度O(32 * n) ≈ O(n)常数项较大但仍是线性。空间复杂度O(1)只使用了固定大小的额外变量。3.1.3 优化解法数字电路设计有限状态自动机上述解法需要遍历32次能否只遍历一次数组就得到结果可以但这需要一点数字电路的知识。我们可以用两个位twos和ones来表示当前位1出现次数的状态对3取模状态00表示出现0次。状态01表示出现1次。状态10表示出现2次。状态11本应表示出现3次但3取模后为0所以自动回到00。我们需要根据当前输入num的每一位设计状态转移方程。推导过程略复杂但最终代码非常精妙class Solution { public: int singleNumber(vectorint nums) { int ones 0, twos 0; for (int num : nums) { // ones num 得到的是“在ones为1且num当前位也为1”的位这些位将进入twos状态01-10 // ~twos 确保了当状态达到10出现两次时不会再接收新的1变成11。 ones (ones ^ num) ~twos; // twos num 得到“在twos为1且num当前位也为1”的位这些位表示出现了三次应清零 ~ones // ones num 是上一步计算出的新ones其中来自状态01-10的部分应转移到twos。 twos (twos ^ num) ~ones; } // 最终出现一次的数存储在ones中状态01出现两次的数存储在twos中状态10 return ones; } };这个解法理解起来有门槛但它是面试中的加分项体现了你对问题本质的深刻理解。如果现场推导不出来可以阐述思路“我们可以用两个比特位模拟状态机只遍历一次”。3.2 变种二LeetCode 260. 只出现一次的数字 III这是“单身狗问题”的另一个经典变种给定一个整数数组nums其中恰好有两个元素只出现一次其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。要求时间复杂度O(n)空间复杂度O(1)。示例输入nums [1,2,1,3,2,5] 输出[3,5] 或 [5,3]3.2.1 思路解析分组异或如果直接对整个数组异或得到的结果xor_all将是两个目标数a和b的异或值即xor_all a ^ b且xor_all必然不为0因为a不等于b。xor_all不为0意味着在二进制表示中至少有一位是1。假设第k位是1那么a和b在第k位上的值一定不同一个为0一个为1。这正是我们将两个数分到不同组的关键。步骤对数组所有元素进行异或得到xor_all a ^ b。找到xor_all中任意一个为1的位通常找最低位的1可以通过diff xor_all -xor_all快速得到这个技巧利用了补码的特性。根据这个位是否为1将原数组分成两组。由于相同的数在该位上的值相同所以成对的数一定会被分到同一组。而a和b因为该位值不同会被分到不同的组。分别对两个组进行异或操作问题退化为LeetCode 136得到的结果就是a和b。3.2.2 代码实现#include vector using namespace std; class Solution { public: vectorint singleNumber(vectorint nums) { // 第一步得到两个单身狗的异或值 long long xor_all 0; // 使用long long防止溢出 for (int num : nums) { xor_all ^ num; } // 第二步找到xor_all中最低位的1分组依据 // 技巧diff xor_all -xor_all // -xor_all 是 xor_all 的补码按位与后得到最低位的1 long long diff xor_all (-xor_all); // 第三步分组异或 int a 0, b 0; for (int num : nums) { if ((num diff) ! 0) { // 如果num在diff位上是1 a ^ num; } else { // 如果num在diff位上是0 b ^ num; } } return {a, b}; } };复杂度分析时间复杂度O(n)两次遍历数组。空间复杂度O(1)使用了固定数量的变量。注意事项这里使用long long是为了处理-xor_all可能对INT_MIN取负导致的溢出问题虽然LeetCode用例通常不会触发。更严谨的写法是int diff xor_all INT_MIN ? xor_all : xor_all (-xor_all);。理解分组依据是核心代码中的diff技巧需要掌握。4. 实战演练与深度扩展理解了原理和变种我们还需要在实战中巩固并思考更广泛的扩展场景。4.1 综合编码实践与测试让我们编写一个完整的程序测试上述所有解法#include iostream #include vector #include unordered_map #include cassert using namespace std; // LeetCode 136 解法位运算 int singleNumber_136(vectorint nums) { int ans 0; for (int num : nums) ans ^ num; return ans; } // LeetCode 137 解法位计数 int singleNumber_137(vectorint nums) { int ans 0; for (int i 0; i 32; i) { int bitSum 0; for (int num : nums) { bitSum ((num i) 1); } if (bitSum % 3) { ans | (1 i); } } return ans; } // LeetCode 260 解法分组异或 vectorint singleNumber_260(vectorint nums) { long long xor_all 0; for (int num : nums) xor_all ^ num; long long diff xor_all (-xor_all); int a 0, b 0; for (int num : nums) { if (num diff) a ^ num; else b ^ num; } return {a, b}; } int main() { cout 测试 LeetCode 136 endl; vectorint test1 {4, 1, 2, 1, 2}; cout 输入: [4,1,2,1,2] endl; cout 输出: singleNumber_136(test1) (期望: 4) endl endl; cout 测试 LeetCode 137 endl; vectorint test2 {0,1,0,1,0,1,99}; cout 输入: [0,1,0,1,0,1,99] endl; cout 输出: singleNumber_137(test2) (期望: 99) endl endl; cout 测试 LeetCode 260 endl; vectorint test3 {1,2,1,3,2,5}; vectorint res singleNumber_260(test3); cout 输入: [1,2,1,3,2,5] endl; cout 输出: [ res[0] , res[1] ] (期望: [3,5] 或 [5,3]) endl; // 验证 assert(singleNumber_136(test1) 4); assert(singleNumber_137(test2) 99); assert((res vectorint{3,5}) || (res vectorint{5,3})); cout \n所有断言通过 endl; return 0; }4.2 扩展思考更一般化的问题如果问题变为“只有一个数字出现一次其余数字出现k次”呢我们可以将位计数法推广int singleNumber_K(vectorint nums, int k) { int result 0; // 假设是32位整数 for (int i 0; i 32; i) { int bitSum 0; for (int num : nums) { bitSum ((num i) 1); } if (bitSum % k ! 0) { // 对k取模 result | (1 i); } } return result; }对于“两个数字出现一次其余出现两次”LeetCode 260可以看作是k2的特例但需要更巧妙的分组。对于“一个数字出现一次其余出现三次”LeetCode 137就是k3。这个方法的时间复杂度是 O(32 * n)空间复杂度 O(1)是通用解法。4.3 边界条件与陷阱排查在实际编码和面试中需要特别注意以下问题整数溢出在求和法或涉及-INT_MIN的操作时如求diff必须考虑溢出。优先使用位运算解法可以避免绝大多数溢出问题。负数处理C/C中右移负数 () 是算术右移高位补符号位。在统计位1的个数时如果使用for (int i0; i32; i)并右移i位对于负数也能正确处理因为我们是按固定32位处理的。但如果用while (num)循环就会出错。diff位的选择在LeetCode 260中选择xor_all中任意一个为1的位都可以。选择最低位的1 (diff xor_all -xor_all) 是最常见的技巧因为它高效且易得。输入验证题目通常保证输入有效非空且满足条件。但在实际工程中应增加检查例如数组是否为空。5. 面试实战技巧与心得总结经过对“单身狗问题”系列的深度剖析最后分享一些从面试官和面试者角度总结的实战心得。5.1 面试回答策略由浅入深不要一上来就甩出位运算答案。先给出最直观的哈希表法分析其时间O(n)、空间O(n)的复杂度。然后指出面试官可能对空间有要求再引出位运算解法。这展示了你的思维过程。解释原理而非背诵代码在阐述异或解法时一定要把四条性质归零、恒等、交换、结合讲清楚并用一个小例子如[4,1,2,1,2]现场演算。证明你真正理解而不是背题。主动思考变种在解答完基础问题后可以主动说“这个问题有一个经典的变种如果其他数字出现三次或者有两个‘单身狗’解法会有所不同……” 这体现了你的知识迁移能力和主动性。讨论复杂度与权衡明确说出位运算解法的时间复杂度O(n)和空间复杂度O(1)。可以提一下哈希表法虽然空间复杂度高但在某些需要知道是哪些数字成对出现的场景下更有用显示你的工程思维。5.2 常见问题与排查记录在自己练习或面试白板编码时你可能会遇到以下问题问题LeetCode 260的代码返回的两个数字顺序不对排查题目明确说明可以按任意顺序返回。你的代码逻辑只要正确找出两个数即可顺序无关紧要。检查分组逻辑是否正确特别是if ((num diff) ! 0)这个条件确保分组一致。问题处理负数时位计数法结果错误排查确认你是在对固定32位进行循环 (for (int i0; i32; i))并且使用(num i) 1来取位。算术右移会保持符号位但与我们按位统计1的个数的目标不冲突。避免使用while (num)的循环。问题状态机解法LeetCode 137完全看不懂如何掌握建议如果时间紧迫掌握位计数通用解法即可它能解决所有“出现k次”的变种且易于理解和记忆。状态机解法可以作为加分项去理解但不必强求现场推导。可以说“我知道还有一种利用位运算状态机只遍历一次的方法其原理是……”5.3 核心要点回顾与个人体会回顾整个“单身狗”系列其核心思想万变不离其宗利用位运算的特性在二进制层面上对信息进行统计和抵消。基础问题出现两次异或的“归零律”和“结合律”是神兵利器直接抵消成对数字。变种一出现三次/多次思路升维从“整体抵消”变为“按位统计再模运算”。这是解决更一般化问题的通用钥匙。变种二两个单身狗核心技巧是“分组”。通过找到两个目标数不同的比特位巧妙地将它们分到两个组每个组内就退化为基础问题。我个人在学习和教学过程中最大的体会是这类问题最好的学习方法不是死记硬背代码而是亲手在纸上进行二进制演算。把一个简单的例子比如[4,1,2,1,2]把每个数字的二进制写出来一步一步做异或亲眼看到数字如何抵消。对于变种问题也亲自画一画每一位上1的个数如何累积、如何取模。这个过程能帮你建立起牢固的直觉。最后C的位操作符,|,^,~,,是实现这些算法的基石务必熟练掌握它们的优先级和运算规则。当你再遇到此类问题时希望你能自信地拿起位运算这把利器优雅地解决它。
