难度: Medium
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1：
输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0] 输出：[-1,0]
示例 3：
输入：nums = [0,1] 输出：[1,0]
提示：
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums 中的其他数字都出现两次运行时间: 23 ms
内存: 18.1 MB
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
a = 0
for num in nums:
a ^= num
mask = 1
while a & mask == 0:
mask <<= 1
a1, a2 = 0, 0
for num in nums:
if num & mask == 0:
a1 ^= num
else:
a2 ^= num
return [a1, a2]
该题解使用了位运算的方式来找到只出现一次的两个数字。首先通过对数组中所有元素进行异或操作，得到的结果是两个只出现一次的数字的异或结果（记为a）。在这个结果中，任何为1的位表示这两个数字在该位上有不同的值。然后，选择结果a中任意一个为1的位（通过循环左移mask并与a做与运算直到结果不为0）作为掩码，依据这个掩码将所有数字分成两组，每组内包括一个只出现一次的数字和若干对出现两次的数字。最后，对这两组数字分别进行异或操作，即可得到这两个只出现一次的数字。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
a = 0
# 第一次遍历，得到两个只出现一次的数字的异或结果
for num in nums:
a ^= num
mask = 1
# 寻找异或结果中任意一个为1的位，用作分组的掩码
while a & mask == 0:
mask <<= 1
a1, a2 = 0, 0
# 第二次遍历，根据掩码分组并分别求异或，得到两个只出现一次的数字
for num in nums:
if num & mask == 0:
a1 ^= num
else:
a2 ^= num
return [a1, a2]
在第一次遍历中，数组内的每个元素都进行了异或操作。异或操作具有以下几个性质：1) 任何数与自身异或的结果为0；2) 任何数与0异或的结果为其自身；3) 异或操作满足交换律和结合律。因此，数组中每对相同的数字（出现两次的数字）都会被抵消掉（因为x^x=0），只留下两个只出现一次的数字的异或结果。这样，所有出现两次的数字确实会在异或过程中被完全抵消。
在选择位掩码时，使用左移而不是右移是因为通常从最低位开始检查，逐步向高位检查，这更符合处理整数的一般习惯。左移和右移在本题中均可使用，主要是为了找到异或结果中任一为1的位，作为分组的依据。无论是左移还是右移，目的都是找到一个有效的分组位，并不影响最终结果。选择左移或右移主要取决于实现习惯，对结果本身没有影响。
在第二次遍历中，掩码是根据两个只出现一次的数字的异或结果中的某一位为1的位置选定的。这保证了这两个数字在此位上一定不同，一个为1另一个为0，因此可以利用这一位将它们分在不同的组。对于其他出现两次的数字，因为每个数字都出现两次，所以无论其在该位是0还是1，它们总是成对出现，并且每对都分配到同一个组中。这样，每组内的所有成对出现的数字都将相互抵消，只留下一个未成对的数字，即只出现一次的数字。因此，掩码能够正确地分组，没有无法正确分组的情况。