找到⽆序数组中出现两次的两个数

🔍【大厂面试真题】系列，带你攻克大厂面试真题，秒变offer收割机！

❓今日问题：找到⽆序数组中出现两次的两个数

❤️一起看看文心快码Baidu Comate给出的答案吧！如果这个问题你也会，也可以在评论区写出你的答案哦～

@comate

在这个问题中，我们需要在一个无序数组中找到两个只出现一次的数字，而其他数字都出现两次。要实现时间复杂度为 O(n) 和空间复杂度为 O(1)，我们可以使用位运算的技巧，但这次情况稍复杂，因为有两个数出现一次。

首先，我们需要理解，如果只有一个数字出现一次，其余数字出现两次，我们可以简单地使用异或运算来找到这个数字。但现在有两个这样的数字，所以我们不能直接应用同样的方法。不过，我们可以稍微修改这个方法来适应当前的问题。

解决方案分为几个步骤：

全体异或：首先，我们遍历整个数组，对所有元素进行异或操作。由于除了两个数字外，其他数字都出现了两次，所以最终的结果将是那两个只出现一次的数字的异或结果。

找到任一出现一次的数字的某一位为1的位：这一步是为了将这两个数字区分开。我们可以通过查找异或结果中任意一个为1的位来实现。这是因为这两个只出现一次的数字在该位上必然是一个为0，另一个为1。

根据这一位将原数组分成两组：现在，我们再次遍历数组，根据上一步找到的位将数组中的数字分成两组。一组包含所有在该位上为1的数字，另一组包含所有在该位上为0的数字。由于我们根据的是两个只出现一次的数字在该位上的不同进行分组，因此这两个数字会被分到不同的组中，而其他成对出现的数字会被分到同一个组中。

对每组分别进行异或操作：最后，我们对每组分别进行异或操作。由于每组中除了一个数字外，其他数字都是成对出现的，所以异或的结果就是那个只出现一次的数字。

下面是这个算法的伪代码实现：


# Step 1: 全体异或
xorResult = 0
for num in nums:
    xorResult ^= num

# Step 2: 找到任一出现一次的数字的某一位为1的位
bit = 1
while (xorResult & bit) == 0:
    bit <<= 1

# Step 3 & 4: 根据这一位将原数组分成两组并分别异或
a, b = 0, 0
for num in nums:
    if num & bit:
        a ^= num
    else:
        b ^= num

# a 和 b 就是两个只出现一次的数字
return a, b
这个算法的时间复杂度是 O(n)，因为我们只遍历了数组两次。空间复杂度是 O(1)，因为我们只使用了有限的额外变量。