寻找两个只出现一次的数字 题目描述 在一个整数数组中，除两个数字外，其他数字都出现了两次。请找出这两个只出现一次的数字。要求时间复杂度为O(n)，空间复杂度为O(1)。 解题思路 这个问题是经典的单数字问题的扩展。如果只有一个数字出现一次，我们可以直接用异或操作解决。但这里有两个不同的数字，我们需要将问题分解。 步骤分解 整体异或得到关键信息 首先，将数组中所有数字进行异或操作。由于相同数字异或结果为0，最终结果等于两个目标数字（假设为a和b）的异或值： xor_all = a ^ b 这个结果不为0（因为a≠b），所以至少有一个二进制位为1。 找到区分a和b的位 在 xor_all 中任意选择一个为1的二进制位（通常选最低位的1）。这个位说明a和b在这一位上不同（一个为0，一个为1）。 例如，如果 xor_all = 6 (二进制110) ，最低位的1在第二位（从右往左，从0开始计数），我们可以用这个位将数组分成两组。 分组异或 根据选定的二进制位，将数组分成两组： 该位为0的数字 该位为1的数字 由于a和b在这一位上不同，它们必然被分到不同的组。同时，相同的数字会被分到同一组。 分别对两组进行异或操作，每组的结果就是其中一个目标数字。 举例说明 数组：[ 1, 2, 1, 3, 2, 5 ] 整体异或： 1^2^1^3^2^5 = 3^5 = 6 (二进制110) 选择最低位的1（第二位），用这个位分组： 第二位为0：1(001), 1(001), 5(101) → 异或结果：1^1^5 = 5 第二位为1：2(010), 3(011), 2(010) → 异或结果：2^3^2 = 3 结果：3和5 关键点 利用异或性质：相同数异或为0，不同数异或能揭示差异位。 通过差异位分组，将问题转化为两个单数字问题。 空间复杂度O(1)，只用了几个变量。