1. 问题背景与核心需求第一次看到这个题目是在准备面试刷题的时候当时觉得只出现一次的数字听起来挺简单的但实际解决起来才发现里面有不少门道。这道题在LeetCode上编号136属于位操作分类的经典题目也是各大厂面试的高频考点。题目描述很简单给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次。要求找出那个只出现一次的数字。比如输入[4,1,2,1,2]输出应该是4。注意题目明确要求算法应该具有线性时间复杂度并且不使用额外空间。这个约束条件直接排除了很多直观但低效的解法。2. 常见解法分析与对比2.1 暴力解法不推荐最直观的想法是双重循环遍历数组对每个元素检查是否在数组中存在另一个相同的元素。这种方法时间复杂度是O(n²)空间复杂度O(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]2.2 哈希表法空间不达标使用哈希表存储元素出现次数最后遍历哈希表找到只出现一次的元素。时间复杂度O(n)但空间复杂度也是O(n)因为需要额外存储空间。def singleNumber(nums): count {} for num in nums: count[num] count.get(num, 0) 1 for num in count: if count[num] 1: return num2.3 数学方法可能溢出利用数学公式2*(abc) - (aabbc) c。需要先求出所有唯一元素的和再减去原数组和。时间复杂度O(n)空间复杂度O(n)需要存储唯一元素集合。def singleNumber(nums): return 2 * sum(set(nums)) - sum(nums)这个方法虽然巧妙但在实际应用中可能遇到整数溢出问题特别是当数组元素值很大时。3. 最优解位操作异或法3.1 异或运算的特性异或运算XOR有几个重要特性任何数和0异或都是它本身a ^ 0 a任何数和自身异或都是0a ^ a 0异或运算满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b3.2 算法实现基于这些特性我们可以将所有数字进行异或运算成对的数字会抵消为0最后剩下的就是只出现一次的数字。def singleNumber(nums): result 0 for num in nums: result ^ num return result这个实现时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了一个额外变量3.3 逐步演算示例以输入[4,1,2,1,2]为例初始result 00 ^ 4 44 ^ 1 55 ^ 2 77 ^ 1 66 ^ 2 4最终返回4确实是只出现一次的数字。4. 边界条件与异常处理4.1 输入验证虽然题目保证非空数组但实际工程中应该考虑空数组情况非整数元素非常大的数组def singleNumber(nums): if not nums: raise ValueError(Input array cannot be empty) result 0 for num in nums: if not isinstance(num, int): raise TypeError(All elements must be integers) result ^ num return result4.2 测试用例设计好的测试用例应该包括常规情况[2,2,1], [4,1,2,1,2]边界情况[1], [0,1,0]负数情况[-1,-1,-2]大数情况[1000000,1,1000000]5. 算法扩展与变种5.1 数字出现两次一个出现一次这是原题的情况用异或法完美解决。5.2 数字出现三次一个出现一次这种情况下异或法不再适用需要使用更复杂的方法比如统计每一位上1的个数。def singleNumber(nums): result 0 for i in range(32): mask 1 i count 0 for num in nums: if num mask: count 1 if count % 3: result | mask return result if result 2**31 else result - 2**325.3 两个数字出现一次当数组中有两个数字只出现一次时需要先通过异或找到这两个数的异或结果然后根据某一位是否为1将数组分成两部分。def singleNumber(nums): xor 0 for num in nums: xor ^ num mask 1 while (xor mask) 0: mask 1 a, b 0, 0 for num in nums: if num mask: a ^ num else: b ^ num return [a, b]6. 实际应用场景虽然这看起来像纯粹的算法题但实际应用场景包括数据校验检测传输或存储过程中是否出现单比特错误加密解密异或操作是很多加密算法的基础资源分配识别唯一可用的资源或设备数据分析找出异常值或特殊样本7. 性能优化与语言特性7.1 Python中的优化在Python中使用内置函数和生成器表达式可以写出更简洁的代码from functools import reduce def singleNumber(nums): return reduce(lambda x, y: x ^ y, nums)7.2 C实现示例int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; } return result; }7.3 Java实现示例public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }8. 常见错误与调试技巧8.1 初学者常见错误忘记初始化result为0混淆了异或(^)和幂运算(**)的符号在C/C中忘记考虑整数溢出在Python中错误处理非整数输入8.2 调试建议打印中间结果在循环中打印每次异或后的result值使用小数组手动演算编写单元测试验证边界条件使用可视化工具观察位的变化9. 相关题目推荐LeetCode 137只出现一次的数字 IILeetCode 260只出现一次的数字 IIILeetCode 268缺失数字LeetCode 389找不同LeetCode 421数组中两个数的最大异或值10. 面试技巧与注意事项先明确问题要求和约束条件从暴力解法开始逐步优化解释清楚异或运算的特性考虑边界条件和异常输入讨论时间空间复杂度准备相关问题的延伸如出现三次的情况提示在实际面试中面试官可能会要求你证明异或解法的正确性或者让你处理更复杂的变种问题。建议在掌握基础解法后深入研究相关变种题目。
1. 问题背景与核心需求第一次看到这个题目是在准备面试刷题的时候当时觉得只出现一次的数字听起来挺简单的但实际解决起来才发现里面有不少门道。这道题在LeetCode上编号136属于位操作分类的经典题目也是各大厂面试的高频考点。题目描述很简单给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次。要求找出那个只出现一次的数字。比如输入[4,1,2,1,2]输出应该是4。注意题目明确要求算法应该具有线性时间复杂度并且不使用额外空间。这个约束条件直接排除了很多直观但低效的解法。2. 常见解法分析与对比2.1 暴力解法不推荐最直观的想法是双重循环遍历数组对每个元素检查是否在数组中存在另一个相同的元素。这种方法时间复杂度是O(n²)空间复杂度O(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]2.2 哈希表法空间不达标使用哈希表存储元素出现次数最后遍历哈希表找到只出现一次的元素。时间复杂度O(n)但空间复杂度也是O(n)因为需要额外存储空间。def singleNumber(nums): count {} for num in nums: count[num] count.get(num, 0) 1 for num in count: if count[num] 1: return num2.3 数学方法可能溢出利用数学公式2*(abc) - (aabbc) c。需要先求出所有唯一元素的和再减去原数组和。时间复杂度O(n)空间复杂度O(n)需要存储唯一元素集合。def singleNumber(nums): return 2 * sum(set(nums)) - sum(nums)这个方法虽然巧妙但在实际应用中可能遇到整数溢出问题特别是当数组元素值很大时。3. 最优解位操作异或法3.1 异或运算的特性异或运算XOR有几个重要特性任何数和0异或都是它本身a ^ 0 a任何数和自身异或都是0a ^ a 0异或运算满足交换律和结合律a ^ b ^ a (a ^ a) ^ b 0 ^ b b3.2 算法实现基于这些特性我们可以将所有数字进行异或运算成对的数字会抵消为0最后剩下的就是只出现一次的数字。def singleNumber(nums): result 0 for num in nums: result ^ num return result这个实现时间复杂度O(n)只需遍历一次数组空间复杂度O(1)只使用了一个额外变量3.3 逐步演算示例以输入[4,1,2,1,2]为例初始result 00 ^ 4 44 ^ 1 55 ^ 2 77 ^ 1 66 ^ 2 4最终返回4确实是只出现一次的数字。4. 边界条件与异常处理4.1 输入验证虽然题目保证非空数组但实际工程中应该考虑空数组情况非整数元素非常大的数组def singleNumber(nums): if not nums: raise ValueError(Input array cannot be empty) result 0 for num in nums: if not isinstance(num, int): raise TypeError(All elements must be integers) result ^ num return result4.2 测试用例设计好的测试用例应该包括常规情况[2,2,1], [4,1,2,1,2]边界情况[1], [0,1,0]负数情况[-1,-1,-2]大数情况[1000000,1,1000000]5. 算法扩展与变种5.1 数字出现两次一个出现一次这是原题的情况用异或法完美解决。5.2 数字出现三次一个出现一次这种情况下异或法不再适用需要使用更复杂的方法比如统计每一位上1的个数。def singleNumber(nums): result 0 for i in range(32): mask 1 i count 0 for num in nums: if num mask: count 1 if count % 3: result | mask return result if result 2**31 else result - 2**325.3 两个数字出现一次当数组中有两个数字只出现一次时需要先通过异或找到这两个数的异或结果然后根据某一位是否为1将数组分成两部分。def singleNumber(nums): xor 0 for num in nums: xor ^ num mask 1 while (xor mask) 0: mask 1 a, b 0, 0 for num in nums: if num mask: a ^ num else: b ^ num return [a, b]6. 实际应用场景虽然这看起来像纯粹的算法题但实际应用场景包括数据校验检测传输或存储过程中是否出现单比特错误加密解密异或操作是很多加密算法的基础资源分配识别唯一可用的资源或设备数据分析找出异常值或特殊样本7. 性能优化与语言特性7.1 Python中的优化在Python中使用内置函数和生成器表达式可以写出更简洁的代码from functools import reduce def singleNumber(nums): return reduce(lambda x, y: x ^ y, nums)7.2 C实现示例int singleNumber(vectorint nums) { int result 0; for (int num : nums) { result ^ num; } return result; }7.3 Java实现示例public int singleNumber(int[] nums) { int result 0; for (int num : nums) { result ^ num; } return result; }8. 常见错误与调试技巧8.1 初学者常见错误忘记初始化result为0混淆了异或(^)和幂运算(**)的符号在C/C中忘记考虑整数溢出在Python中错误处理非整数输入8.2 调试建议打印中间结果在循环中打印每次异或后的result值使用小数组手动演算编写单元测试验证边界条件使用可视化工具观察位的变化9. 相关题目推荐LeetCode 137只出现一次的数字 IILeetCode 260只出现一次的数字 IIILeetCode 268缺失数字LeetCode 389找不同LeetCode 421数组中两个数的最大异或值10. 面试技巧与注意事项先明确问题要求和约束条件从暴力解法开始逐步优化解释清楚异或运算的特性考虑边界条件和异常输入讨论时间空间复杂度准备相关问题的延伸如出现三次的情况提示在实际面试中面试官可能会要求你证明异或解法的正确性或者让你处理更复杂的变种问题。建议在掌握基础解法后深入研究相关变种题目。
