本文首发于微信公众号：图解算法
题目
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
举例：{2,4,3,6,3,2,5,5}
这个数组中只出现一次的两个数分别是4和6。怎么找到这个两个数字呢？
我们先不看找到俩个的情况，先看这样一个问题，如何在一个数组中找到一个只出现一次的数字呢？比如数组：{4,5,5}，唯一一个只出现一次的数字是4。
我们知道异或的一个性质是：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字。比如数组{4,5,5}，我们先用数组中的第一个元素4（二进制形式：0100）和数组中的第二个元素5（二进制形式：0101）进行异或操作，0100和0101异或得到0001，用这个得到的元素与数组中的三个元素5（二进制形式：0101）进行异或操作，0001和0101异或得到0100，正好是结果数字4。这是因为数组中相同的元素异或是为0的，因此就只剩下那个不成对的孤苦伶仃元素。
现在好了，我们已经知道了如何找到一个数组中找到一个只出现一次的数字，那么我们如何在一个数组中找到两个只出现一次的数字呢？如果，我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。
我们还是从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。
举例：{2,4,3,6,3,2,5,5}
我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是
代码
C++
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
//先将所有元素异或。最后剩下的数是只出现一次的数字num1,num2的异或
int k = 0; // 0^x = x
for(int i : nums) //所有数字异或
k ^= i;
int mask = 1;
while((k&1)!=1)
{
//从后往前找到最低位的1；
k= k>>1;
mask = mask<<1;
}
int num1=0,num2=0;
//用这个mask就可以把两个数区分开，
for(int i : nums)
{
if((i&mask)!=0) num1^=i; // mask指定的那一位是num1，num2的不同
else num2^=i;
}
return {num1,num2};
}
};
Java
public int[] singleNumbers(int[] nums) {
int sum=0;
//将数组所有元素进行异或，最后的结果一定是那两个单一数字的异或结果。看上图示例
//用示例[4,4,6,1]最后的抑或结果就是 6和1异或的结果 7
for (int i = 0; i <nums.length ; i++) {
sum^=nums[i];
}
int first = 1;
//通过与运算找到result第一个不为0的首位，7=>0111，也就是第一位
while((sum&first)==0){
first=first<<1;
}
//first为1，所以我们可以根据数组元素的二进制低位第一位是否为1，将数组分为2类，
// 示例数组可以分为 低位第一位为0：[4,4,6] 低位第一位为1：[1]
//此时再将两个数组两两异或就可以得到最终结果。
int result[]=new int[2];
for(int i=0;i<nums.length;i++){
//将数组分类。
if((nums[i]&first)==0){
result[0]^=nums[i];
}
else{
result[1]^=nums[i];
}
}
return result;
}
Python
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
ret = 0 # 所有数字异或的结果
a = 0
b = 0
for n in nums:
ret ^= n
# 找到第一位不是0的
h = 1
while(ret & h == 0):
h <<= 1
for n in nums:
# 根据该位是否为0将其分为两组
if (h & n == 0):
a ^= n
else:
b ^= n
return [a, b]
JS
const singleNumbers = (nums) => {
// 计算异或值
let num1 = 0
for (let i = 0; i < nums.length; i++) {
num1 = num1 ^ nums[i];
}
// 通过与(&)选定1的位置
let count = 1
while((num1&count) === 0) {
count = count * 2
}
// 分组
let num2 = 0
let num3 = 0
for (let i = 0; i < nums.length; i++) {
const num = nums[i]
if ((num & count) === 0) {
num2 = num2^num
} else {
num3 = num3^num
}
}
return [num2, num3]
}
