1. 问题背景与核心思路在算法面试和日常编程中找出数组中只出现一次的数字是一道经典题目。题目描述很简单给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次找出那个只出现一次的数字。这道题看似简单但考察了程序员对位运算的理解和灵活应用能力。常规解法可能会想到使用哈希表统计数字出现次数但这样会消耗额外的存储空间。更高效的解法是利用异或运算XOR的特性实现时间复杂度O(n)且空间复杂度O(1)的优雅解决方案。提示异或运算在算法题中经常被用来处理成对出现的问题是位运算中最常用的操作之一。2. 异或运算的特性解析2.1 异或运算的基本性质异或运算XOR是一种二进制位运算符号为^。它的运算规则是两个位相同为0相异为1。具体来说0 ^ 0 00 ^ 1 11 ^ 0 11 ^ 1 0对于解决这个问题我们需要特别关注异或运算的以下几个关键特性自反性任何数和自己异或的结果都是0。即 A ^ A 0恒等性任何数和0异或的结果都是它本身。即 A ^ 0 A交换律和结合律异或运算满足交换律和结合律。即 A ^ B ^ A A ^ A ^ B 0 ^ B B2.2 为什么异或能解决这个问题假设我们有一个数组 [2,1,4,1,2]按照题目描述数字4只出现一次其他数字都出现两次。如果我们把所有数字进行异或运算2 ^ 1 ^ 4 ^ 1 ^ 2 (2 ^ 2) ^ (1 ^ 1) ^ 4 // 利用交换律重新排列 0 ^ 0 ^ 4 // 自反性相同数字异或为0 4 // 恒等性0与任何数异或等于该数可以看到成对出现的数字通过异或运算都变成了0最后剩下的就是只出现一次的数字。3. Java实现详解3.1 代码实现class Solution { public int singleNumber(int[] nums) { // 定义初始值为0 int result 0; // 遍历数组中的每个数字 for(int num : nums){ // 对每个数字执行异或运算 result result ^ num; } return result; } }3.2 代码逐行解析初始化result为0因为0与任何数异或都等于该数本身所以初始值为0不会影响最终结果。for-each循环遍历数组这种写法简洁且不易出错特别适合这种需要遍历整个数组的场景。异或运算累积每次将当前result与数组元素进行异或运算利用异或的特性逐步消去成对出现的数字。返回最终结果遍历完成后result中存储的就是只出现一次的数字。3.3 复杂度分析时间复杂度O(n)只需要遍历一次数组。空间复杂度O(1)只使用了常数级别的额外空间。4. 实际应用中的注意事项4.1 边界条件处理虽然题目保证非空数组且存在唯一解但在实际工程中我们应该考虑空数组情况可以抛出异常或返回特定值。多个唯一数字题目保证只有一个但实际应用中可能需要验证。// 增强健壮性的版本 class Solution { public int singleNumber(int[] nums) { if(nums null || nums.length 0) { throw new IllegalArgumentException(数组不能为空); } int result 0; for(int num : nums){ result ^ num; } // 可选验证确实只有一个唯一数字 // 需要额外遍历统计出现次数 return result; } }4.2 性能优化技巧使用位运算复合赋值result ^ num比result result ^ num更简洁高效。避免不必要的变量直接使用参数nums不需要额外复制数组。考虑JVM优化现代JVM对简单的循环有很好的优化保持代码简洁即可。4.3 常见错误与调试初始值错误有人可能想初始化为第一个元素这样会导致第一个元素被异或两次。错误示例int result nums[0]; for(int i1; inums.length; i)...这样写虽然也能得到正确结果但逻辑不够直观容易出错。运算符优先级混淆异或运算优先级较低复合运算时要注意加括号。例如a b ^ c d不同于a b ^ (c d)数据类型溢出虽然题目通常使用int但要考虑大数情况必要时使用long。5. 扩展思考与变种问题5.1 如果数字出现三次怎么办当数字出现三次而非两次时简单的异或方法不再适用。这时可以考虑位统计法统计所有数字每一位上1的个数如果不能被3整除则唯一数字该位为1。哈希表法虽然空间复杂度增加但通用性强。// 位统计法解决数字出现三次的问题 class Solution { public int singleNumber(int[] nums) { int result 0; for(int i0; i32; i) { int sum 0; for(int num : nums) { sum (num i) 1; } if(sum % 3 ! 0) { result | (1 i); } } return result; } }5.2 如果有两个唯一数字怎么办当数组中有两个数字只出现一次其他都出现两次时解决方案会更复杂首先对所有数字异或得到两个唯一数字的异或结果。找到这个结果中任意一个为1的位说明两个数字在这一位不同。根据这一位将数组分成两组分别异或得到两个数字。// 找出两个唯一数字的解法 class Solution { public int[] singleNumber(int[] nums) { int xor 0; for(int num : nums) { xor ^ num; } // 找到最右边的1 int mask 1; while((xor mask) 0) { mask 1; } int num1 0, num2 0; for(int num : nums) { if((num mask) 0) { num1 ^ num; } else { num2 ^ num; } } return new int[]{num1, num2}; } }5.3 实际工程中的应用场景数据校验异或校验常用于简单的数据传输校验。加密算法某些轻量级加密会使用异或运算。状态切换用异或来切换布尔状态如flag ^ true。图形处理异或绘图模式可以实现特殊的图形效果。6. 算法比较与选择6.1 异或法 vs 哈希表法特性异或法哈希表法时间复杂度O(n)O(n)空间复杂度O(1)O(n)适用场景数字成对出现通用场景实现难度需要理解位运算简单直观扩展性有限特定问题强可统计任意次数6.2 何时选择异或解法题目明确要求空间复杂度O(1)数字出现次数有特定规律如多数成对需要展示位运算技巧的面试场景对性能有极致要求的嵌入式环境6.3 何时选择其他解法数字出现次数无固定规律需要统计更多信息如所有唯一数字代码可读性优先的场景处理非整数数据时7. 测试用例设计全面的测试用例应该包括基础用例输入[2,2,1] 输出1输入[4,1,2,1,2] 输出4边界用例最小数组[1] 输出1最大数字[Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE] 输出Integer.MIN_VALUE特殊用例负数情况[-1,-1,-2] 输出-2零的情况[0,1,0] 输出1性能测试大数组测试100万个元素其中1个唯一// 示例测试代码 public class SolutionTest { Test public void testSingleNumber() { Solution solution new Solution(); assertEquals(1, solution.singleNumber(new int[]{2,2,1})); assertEquals(4, solution.singleNumber(new int[]{4,1,2,1,2})); assertEquals(1, solution.singleNumber(new int[]{1})); assertEquals(Integer.MIN_VALUE, solution.singleNumber(new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE})); assertEquals(-2, solution.singleNumber(new int[]{-1,-1,-2})); assertEquals(1, solution.singleNumber(new int[]{0,1,0})); } }8. 位运算的其他妙用除了解决这个问题异或运算还有许多其他有趣的用途交换两个数int a 5, b 10; a ^ b; b ^ a; a ^ b; // 现在a10, b5判断奇偶if((num 1) 0) { // 偶数 }取绝对值对于整数int abs (num ^ (num 31)) - (num 31);加密解密// 简单加密 byte data 0x45; byte key 0x2A; byte encrypted (byte)(data ^ key); byte decrypted (byte)(encrypted ^ key);寻找缺失的数字 在1到n的连续数字中找出缺失的一个可以用异或所有数字和所有索引的方法。9. 面试中的考察点当面试官提出这个问题时通常考察以下几个方面基础编码能力能否正确实现基本功能。算法思维是否能想到最优解而非暴力解法。位运算理解对异或特性的理解和应用。问题分析能否解释清楚算法为什么有效。边界处理是否考虑特殊输入情况。扩展思考能否讨论变种问题的解法。在面试中建议按照以下步骤回答先提出哈希表等直观解法分析复杂度。然后提出异或解法解释其优势。详细说明异或运算的相关性质。讨论可能的边界情况和异常处理。如有时间可以简要提及变种问题的思路。10. 性能实测与优化为了验证异或解法的效率我们可以进行简单的性能测试public class PerformanceTest { public static void main(String[] args) { // 准备测试数据1百万个元素 int[] nums new int[1_000_000]; Arrays.fill(nums, 1); nums[500_000] 2; // 唯一数字 Solution solution new Solution(); // 预热 for(int i0; i10; i) { solution.singleNumber(nums); } // 正式测试 long start System.nanoTime(); int result solution.singleNumber(nums); long duration System.nanoTime() - start; System.out.println(结果: result); System.out.println(耗时: duration 纳秒); } }在我的测试环境中JDK 17i7-11800H处理100万个元素的数组大约需要1-2毫秒显示出极高的效率。相比之下哈希表解法通常需要5-10毫秒并且内存使用明显更高。对于极致的性能优化可以考虑使用数组而非集合如果数字范围有限可以用数组代替哈希表。并行处理对于超大数组可以分块并行异或最后合并结果。JVM特定优化使用-XX:AggressiveOpts等JVM参数。然而在大多数情况下简单的异或解法已经足够高效过早优化往往得不偿失。 
长河君 · 2026/11/4 12:27:02 · 阅读 1.2k 利用异或运算高效找出数组中唯一数字
1. 问题背景与核心思路在算法面试和日常编程中找出数组中只出现一次的数字是一道经典题目。题目描述很简单给定一个非空整数数组其中某个元素只出现一次其余每个元素均出现两次找出那个只出现一次的数字。这道题看似简单但考察了程序员对位运算的理解和灵活应用能力。常规解法可能会想到使用哈希表统计数字出现次数但这样会消耗额外的存储空间。更高效的解法是利用异或运算XOR的特性实现时间复杂度O(n)且空间复杂度O(1)的优雅解决方案。提示异或运算在算法题中经常被用来处理成对出现的问题是位运算中最常用的操作之一。2. 异或运算的特性解析2.1 异或运算的基本性质异或运算XOR是一种二进制位运算符号为^。它的运算规则是两个位相同为0相异为1。具体来说0 ^ 0 00 ^ 1 11 ^ 0 11 ^ 1 0对于解决这个问题我们需要特别关注异或运算的以下几个关键特性自反性任何数和自己异或的结果都是0。即 A ^ A 0恒等性任何数和0异或的结果都是它本身。即 A ^ 0 A交换律和结合律异或运算满足交换律和结合律。即 A ^ B ^ A A ^ A ^ B 0 ^ B B2.2 为什么异或能解决这个问题假设我们有一个数组 [2,1,4,1,2]按照题目描述数字4只出现一次其他数字都出现两次。如果我们把所有数字进行异或运算2 ^ 1 ^ 4 ^ 1 ^ 2 (2 ^ 2) ^ (1 ^ 1) ^ 4 // 利用交换律重新排列 0 ^ 0 ^ 4 // 自反性相同数字异或为0 4 // 恒等性0与任何数异或等于该数可以看到成对出现的数字通过异或运算都变成了0最后剩下的就是只出现一次的数字。3. Java实现详解3.1 代码实现class Solution { public int singleNumber(int[] nums) { // 定义初始值为0 int result 0; // 遍历数组中的每个数字 for(int num : nums){ // 对每个数字执行异或运算 result result ^ num; } return result; } }3.2 代码逐行解析初始化result为0因为0与任何数异或都等于该数本身所以初始值为0不会影响最终结果。for-each循环遍历数组这种写法简洁且不易出错特别适合这种需要遍历整个数组的场景。异或运算累积每次将当前result与数组元素进行异或运算利用异或的特性逐步消去成对出现的数字。返回最终结果遍历完成后result中存储的就是只出现一次的数字。3.3 复杂度分析时间复杂度O(n)只需要遍历一次数组。空间复杂度O(1)只使用了常数级别的额外空间。4. 实际应用中的注意事项4.1 边界条件处理虽然题目保证非空数组且存在唯一解但在实际工程中我们应该考虑空数组情况可以抛出异常或返回特定值。多个唯一数字题目保证只有一个但实际应用中可能需要验证。// 增强健壮性的版本 class Solution { public int singleNumber(int[] nums) { if(nums null || nums.length 0) { throw new IllegalArgumentException(数组不能为空); } int result 0; for(int num : nums){ result ^ num; } // 可选验证确实只有一个唯一数字 // 需要额外遍历统计出现次数 return result; } }4.2 性能优化技巧使用位运算复合赋值result ^ num比result result ^ num更简洁高效。避免不必要的变量直接使用参数nums不需要额外复制数组。考虑JVM优化现代JVM对简单的循环有很好的优化保持代码简洁即可。4.3 常见错误与调试初始值错误有人可能想初始化为第一个元素这样会导致第一个元素被异或两次。错误示例int result nums[0]; for(int i1; inums.length; i)...这样写虽然也能得到正确结果但逻辑不够直观容易出错。运算符优先级混淆异或运算优先级较低复合运算时要注意加括号。例如a b ^ c d不同于a b ^ (c d)数据类型溢出虽然题目通常使用int但要考虑大数情况必要时使用long。5. 扩展思考与变种问题5.1 如果数字出现三次怎么办当数字出现三次而非两次时简单的异或方法不再适用。这时可以考虑位统计法统计所有数字每一位上1的个数如果不能被3整除则唯一数字该位为1。哈希表法虽然空间复杂度增加但通用性强。// 位统计法解决数字出现三次的问题 class Solution { public int singleNumber(int[] nums) { int result 0; for(int i0; i32; i) { int sum 0; for(int num : nums) { sum (num i) 1; } if(sum % 3 ! 0) { result | (1 i); } } return result; } }5.2 如果有两个唯一数字怎么办当数组中有两个数字只出现一次其他都出现两次时解决方案会更复杂首先对所有数字异或得到两个唯一数字的异或结果。找到这个结果中任意一个为1的位说明两个数字在这一位不同。根据这一位将数组分成两组分别异或得到两个数字。// 找出两个唯一数字的解法 class Solution { public int[] singleNumber(int[] nums) { int xor 0; for(int num : nums) { xor ^ num; } // 找到最右边的1 int mask 1; while((xor mask) 0) { mask 1; } int num1 0, num2 0; for(int num : nums) { if((num mask) 0) { num1 ^ num; } else { num2 ^ num; } } return new int[]{num1, num2}; } }5.3 实际工程中的应用场景数据校验异或校验常用于简单的数据传输校验。加密算法某些轻量级加密会使用异或运算。状态切换用异或来切换布尔状态如flag ^ true。图形处理异或绘图模式可以实现特殊的图形效果。6. 算法比较与选择6.1 异或法 vs 哈希表法特性异或法哈希表法时间复杂度O(n)O(n)空间复杂度O(1)O(n)适用场景数字成对出现通用场景实现难度需要理解位运算简单直观扩展性有限特定问题强可统计任意次数6.2 何时选择异或解法题目明确要求空间复杂度O(1)数字出现次数有特定规律如多数成对需要展示位运算技巧的面试场景对性能有极致要求的嵌入式环境6.3 何时选择其他解法数字出现次数无固定规律需要统计更多信息如所有唯一数字代码可读性优先的场景处理非整数数据时7. 测试用例设计全面的测试用例应该包括基础用例输入[2,2,1] 输出1输入[4,1,2,1,2] 输出4边界用例最小数组[1] 输出1最大数字[Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE] 输出Integer.MIN_VALUE特殊用例负数情况[-1,-1,-2] 输出-2零的情况[0,1,0] 输出1性能测试大数组测试100万个元素其中1个唯一// 示例测试代码 public class SolutionTest { Test public void testSingleNumber() { Solution solution new Solution(); assertEquals(1, solution.singleNumber(new int[]{2,2,1})); assertEquals(4, solution.singleNumber(new int[]{4,1,2,1,2})); assertEquals(1, solution.singleNumber(new int[]{1})); assertEquals(Integer.MIN_VALUE, solution.singleNumber(new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MAX_VALUE})); assertEquals(-2, solution.singleNumber(new int[]{-1,-1,-2})); assertEquals(1, solution.singleNumber(new int[]{0,1,0})); } }8. 位运算的其他妙用除了解决这个问题异或运算还有许多其他有趣的用途交换两个数int a 5, b 10; a ^ b; b ^ a; a ^ b; // 现在a10, b5判断奇偶if((num 1) 0) { // 偶数 }取绝对值对于整数int abs (num ^ (num 31)) - (num 31);加密解密// 简单加密 byte data 0x45; byte key 0x2A; byte encrypted (byte)(data ^ key); byte decrypted (byte)(encrypted ^ key);寻找缺失的数字 在1到n的连续数字中找出缺失的一个可以用异或所有数字和所有索引的方法。9. 面试中的考察点当面试官提出这个问题时通常考察以下几个方面基础编码能力能否正确实现基本功能。算法思维是否能想到最优解而非暴力解法。位运算理解对异或特性的理解和应用。问题分析能否解释清楚算法为什么有效。边界处理是否考虑特殊输入情况。扩展思考能否讨论变种问题的解法。在面试中建议按照以下步骤回答先提出哈希表等直观解法分析复杂度。然后提出异或解法解释其优势。详细说明异或运算的相关性质。讨论可能的边界情况和异常处理。如有时间可以简要提及变种问题的思路。10. 性能实测与优化为了验证异或解法的效率我们可以进行简单的性能测试public class PerformanceTest { public static void main(String[] args) { // 准备测试数据1百万个元素 int[] nums new int[1_000_000]; Arrays.fill(nums, 1); nums[500_000] 2; // 唯一数字 Solution solution new Solution(); // 预热 for(int i0; i10; i) { solution.singleNumber(nums); } // 正式测试 long start System.nanoTime(); int result solution.singleNumber(nums); long duration System.nanoTime() - start; System.out.println(结果: result); System.out.println(耗时: duration 纳秒); } }在我的测试环境中JDK 17i7-11800H处理100万个元素的数组大约需要1-2毫秒显示出极高的效率。相比之下哈希表解法通常需要5-10毫秒并且内存使用明显更高。对于极致的性能优化可以考虑使用数组而非集合如果数字范围有限可以用数组代替哈希表。并行处理对于超大数组可以分块并行异或最后合并结果。JVM特定优化使用-XX:AggressiveOpts等JVM参数。然而在大多数情况下简单的异或解法已经足够高效过早优化往往得不偿失。