难度: Medium
整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。
示例 1：
输入：sockets = [4, 5, 2, 4, 6, 6] 输出：[2,5] 或 [5,2]
示例 2：
输入：sockets = [1, 2, 4, 1, 4, 3, 12, 3] 输出：[2,12] 或 [12,2]
提示：
2 <= sockets.length <= 10000运行时间: 60 ms
内存: 15.6 MB
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
x, y, n, m = 0, 0, 0, 1
for num in nums:
n ^= num
while n & m == 0:
m <<= 1
for num in nums:
if num & m:
x ^= num
else:
y ^= num
return x, y
题解的思路是利用异或运算的性质，其中相同的数字异或的结果是0，而任何数字和0异或是它本身。首先，对数组中所有元素进行一次全体异或运算，结果是那两个只出现一次的数的异或结果（因为成对的数字异或会变为0）。然后，从这个结果中找到任意一个为1的位，这意味着这两个数在这一位上一个是0，另一个是1。接下来，以这个位是否为1为标准，将数组分成两部分，各自对这两部分再次进行异或运算。这样就可以分别得到这两个只出现一次的数字。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
x, y, n, m = 0, 0, 0, 1
# 对所有数字进行异或，找到两个单独数字的异或结果
for num in nums:
n ^= num
# 找到异或结果中第一个为1的位，这表示两个数在这一位上不同
while n & m == 0:
m <<= 1
# 根据这一位的值将数组分成两部分，并分别对这两部分进行异或
for num in nums:
if num & m:
x ^= num
else:
y ^= num
return x, y
异或操作在这种问题中非常有用，因为它具有一些独特的性质：任何数与0异或结果仍为原数，任何数与其自身异或结果为0。当数组中的数除了两个特定的数只出现一次外，其余的数都出现两次时，对整个数组进行异或运算，成对出现的数字由于异或自身等于0会相互抵消，最后的结果就是那两个只出现一次的数字的异或结果。这个结果中的每个1都代表这两个数在该位上的差异，可以用来区分这两个数。
在异或的结果中，一个位如果是1，表示这两个只出现一次的数字在这一位上必定是不同的（一个是0，另一个是1）。因此，这个位确实可以用来区分这两个数字。通过将数组中的数字根据这一位的值是0还是1分成两组，可以保证每组内包含一个只出现一次的数字，而成对出现的数字会被分到相同的组中。
是的，这种方法仍然非常高效，因为它的时间复杂度主要由两次遍历数组决定，即O(2n) ≈ O(n)，其中n是数组的长度。首先一次遍历用于计算所有数字的异或结果，第二次遍历用于分组和计算两个只出现一次的数字。这种方法的空间复杂度也是O(1)，因为除了输入数组外，只需要有限的额外空间来存储中间结果和输出。因此，即使对于非常大的数组，这种方法也能保持较高的效率。
这个循环的执行次数取决于整型数字的位数。在大多数现代计算机中，整数通常是32位或64位。循环每次将位标记向左移位，直到找到n中的第一个1。在最坏的情况下，如果这个1位于最高位，对于32位整数，循环可能会执行32次；对于64位整数，可能会执行64次。