题目
整数数组
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
思考
- 因为这题的要求：时间复杂度 O(n)，空间复杂度O(1) ，所以暴力法和哈希表统计法不可行
- 另一种想法是双指针法：右指针不断向右移动，当找到与左指针上的值相同的值时，左右指针同时向右移动一位，但是仔细思考可以发现，左指针可能指向右指针已经遍历过的位置，如果使用额外变量记录已经遍历过的位置，那空间复杂度可能达不到O(1)的要求
- 其实，这道题的一个特点是，出现偶数次的相同数字不是目标数字，看到这种特点，我们应该想到异或运算：两个相同数字异或结果为0。所以，如果将所有数字异或起来，最后留下的数字就是要找的数字
- 这时候出现了一个问题：虽然有配对的数字会被消去，但是撞色的数字通过异或会被杂糅为一个结果，我们需要一个方法将其分开。由异或的特点可知，当两个不相同的数字异或后，结果就是在不相同的位上为1，所以我们根据结果，再遍历一次，通过结果进行分类，将所有的数字以这一位数字是否与结果相同分成两组，分别异或，最终那两个撞色的数字就不会被分到同一组，最终也就不会因为异或被杂糅在一起
解法
class Solution {
public:
// 寻找数组中出现奇数次的两个数字
vector<int> sockCollocation(vector<int>& nums) {
int xorResult = 0, bitMask = 1, numA = 0, numB = 0;
for(auto &num : nums) xorResult ^= num; // 求出数组中所有数字的异或结果
while(!(xorResult & bitMask)) bitMask <<= 1; // 找到异或结果中为1的最低位
for(auto &num : nums) {
bitMask&num ? numA ^= num : numB ^= num;
}// 根据最低位将数字分为两组，并分别进行异或操作
return vector<int>{numA, numB}; // 返回结果数组
}
};
