LeetCode-Book/leetbook_ioa/docs/LCR 177. 撞色搭配.md

解题思路：

题目要求时间复杂度 O(N) ，空间复杂度 O(1) ，因此首先排除 暴力法 和 哈希表统计法 。

简化问题： 一个整型数组 sockets 里除 一个 数字之外，其他数字都出现了两次。

设整型数组 sockets 中出现一次的数字为 x ，出现两次的数字为 a, a, b, b, ... ，即：

sockets = [a, a, b, b, ..., x]

异或运算有个重要的性质，两个相同数字异或为 0 ，即对于任意整数 a 有 a \oplus a = 0 。因此，若将 sockets 中所有数字执行异或运算，留下的结果则为 出现一次的数字 $x$ ，即：

\begin{aligned}
& \ \ a \oplus a \oplus b \oplus b \oplus ... \oplus x \\
= & \ \ 0 \oplus 0 \oplus ... \oplus x \\
= & \ \ x
\end{aligned}

异或运算满足交换律 a \oplus b = b \oplus a ，即以上运算结果与 sockets 的元素顺序无关。代码如下：

def singleNumber(self, sockets: List[int]) -> List[int]:
    x = 0
    for num in sockets:  # 1. 遍历 sockets 执行异或运算
        x ^= num      
    return x;         # 2. 返回出现一次的数字 x

public int[] singleNumber(int[] sockets) {
    int x = 0;
    for(int num : sockets)  // 1. 遍历 sockets 执行异或运算
        x ^= num;
    return x;            // 2. 返回出现一次的数字 x
}

vector<int> singleNumber(vector<int>& sockets) {
    int x = 0;
    for(int num : sockets)  // 1. 遍历 sockets 执行异或运算
        x ^= num;
    return x;            // 2. 返回出现一次的数字 x
}

下图中的 nums 对应本题的 sockets 。

{:align=center width=500}

本题难点： 数组 sockets 有 两个 只出现一次的数字，因此无法通过异或直接得到这两个数字。

设两个只出现一次的数字为 x , y ，由于 x \ne y ，则 x 和 y 二进制至少有一位不同（即分别为 0 和 1 ），根据此位可以将 sockets 拆分为分别包含 x 和 y 的两个子数组。

易知两子数组都满足 「除一个数字之外，其他数字都出现了两次」。因此，仿照以上简化问题的思路，分别对两子数组遍历执行异或操作，即可得到两个只出现一次的数字 x, y 。

算法流程：

1. 遍历 sockets 执行异或：

• 设整型数组 sockets = [a, a, b, b, ..., x, y] ，对 sockets 中所有数字执行异或，得到的结果为 x \oplus y ，即：

\begin{aligned}
& \ \ a \oplus a \oplus b \oplus b \oplus ... \oplus x \oplus y \\
= & \ \ 0 \oplus 0 \oplus ... \oplus x \oplus y \\
= & \ \ x \oplus y
\end{aligned}

2. 循环左移计算 m ：

• 根据异或运算定义，若整数 x \oplus y 某二进制位为 1 ，则 x 和 y 的此二进制位一定不同。换言之，找到 x \oplus y 某为 1 的二进制位，即可将数组 sockets 拆分为上述的两个子数组。根据与运算特点，可知对于任意整数 a 有：

  • 若 a \& 0001 \ne 0 ，则 a 的第一位为 1 ；
  • 若 a \& 0010 \ne 0 ，则 a 的第二位为 1 ；
  • 以此类推……

• 因此，初始化一个辅助变量 m = 1 ，通过与运算从右向左循环判断，可 获取整数 x \oplus y 首位 $1$ ，记录于 m 中，代码如下：

while z & m == 0: # m 循环左移一位，直到 z & m ！= 0
    m <<= 1

while(z & m == 0) // m 循环左移一位，直到 z & m ！= 0
    m <<= 1

while(z & m == 0) // m 循环左移一位，直到 z & m ！= 0
    m <<= 1

3. 拆分 sockets 为两个子数组：
4. 分别遍历两个子数组执行异或：

• 通过遍历判断 sockets 中各数字和 m 做与运算的结果，可将数组拆分为两个子数组，并分别对两个子数组遍历求异或，则可得到两个只出现一次的数字，代码如下：

for num in sockets:
    if num & m: x ^= num  # 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或
    else: y ^= num        # 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或
return x, y               # 遍历异或完毕，返回只出现一次的数字 x 和 y

for(int num: sockets) {
    if((num & m) != 0) x ^= num;  // 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或
    else y ^= num;                // 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或
}
return new int[] {x, y};          // 遍历异或完毕，返回只出现一次的数字 x 和 y

for(int num : sockets) {
    if(num & m) x ^= num;   // 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或
    else y ^= num;          // 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或
}
return vector<int> {x, y};  // 遍历异或完毕，返回只出现一次的数字 x 和 y

5. 返回值：

• 返回只出现一次的数字 x, y 即可。

下图中的 nums 对应本题的 sockets 。

复杂度分析：

• 时间复杂度 O(N) ： 线性遍历 sockets 使用 O(N) 时间，遍历 x \oplus y 二进制位使用 O(32) = O(1) 时间。
• 空间复杂度 O(1) ： 辅助变量 a , b , x , y 使用常数大小额外空间。

代码：

class Solution:
    def sockCollocation(self, sockets: List[int]) -> List[int]:
        x, y, n, m = 0, 0, 0, 1
        for num in sockets:      # 1. 遍历异或
            n ^= num
        while n & m == 0:        # 2. 循环左移，计算 m
            m <<= 1       
        for num in sockets:      # 3. 遍历 sockets 分组
            if num & m: x ^= num # 4. 当 num & m != 0
            else: y ^= num       # 4. 当 num & m == 0
        return x, y              # 5. 返回出现一次的数字

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : sockets)            // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)               // 2. 循环左移，计算 m
            m <<= 1;
        for(int num: sockets) {           // 3. 遍历 sockets 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }
}

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : sockets)      // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)         // 2. 循环左移，计算 m
            m <<= 1;
        for(int num : sockets) {    // 3. 遍历 sockets 分组
            if(num & m) x ^= num;   // 4. 当 num & m != 0
            else y ^= num;          // 4. 当 num & m == 0
        }
        return vector<int> {x, y};  // 5. 返回出现一次的数字
    }
};