一、问题

整数数组 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

二、思路

效仿单个单身狗，只需要按位异或所有数据，即可得到单个单身狗。

当两个单身狗时，可以将两个单身狗拆开。

三、代码

    // 转化成两个单独的单身狗问题：分拆

int* sockCollocation(int* sockets, int socketsSize, int* returnSize) {

    int num = 0;

    for (int i = 0; i < socketsSize; i++)
    {
        num ^= sockets[i];
    }

    // 通过按位异或 ，确定第 i 位为 1 ，分离两个单身狗

    //任何数 & 1， 结果为 0 或 1
    
    int pos = 0;

    for (int i = 0; i < 32; i++)
    {
        if ( (num >> i) & 1 == 1 )   //右移
        {
            pos = i;        //第i位 不同，按照此位分开
        }
    }

    //分离：只需分离两个单身狗即可

    int dog1 = 0;
    int dog2 = 0;

    for (int i = 0; i < socketsSize; i++)
    {
        if ( (sockets[i]>>pos) & 1 ==  1)
        {
            dog1 ^= sockets[i]; 
        }

        else
        {
            dog2 ^= sockets[i];
        }

    }

    int* a = (int*)malloc(sizeof(int) * 2);     //要动态内存开辟，否则失效

    a[0] = dog1;
    a[1] = dog2;

    *returnSize = 2;    //表示返回数据的多少

    return a;

}

四、代码讲解

1.拆分

 //分离：只需分离两个单身狗即可

 

 int pos = 0;

    for (int i = 0; i < 32; i++)
    {
        if ( (num >> i) & 1 == 1 )   //右移
        {
            pos = i;        //第i位 不同，按照此位分开
        }
    }

通过按位右移，得到某一位为1。（相同为0，相异为1，所以第pos位，两个单身狗不同，按照此位置，将两个单身狗分开。）

2.得到单身狗

将两个单身狗，按第 pos 位不同，分别按位异或不同的数组数据。

    for (int i = 0; i < socketsSize; i++)
    {
        if ( (sockets[i]>>pos) & 1 ==  1)
        {
            dog1 ^= sockets[i]; 
        }

        else
        {
            dog2 ^= sockets[i];
        }

    }

3.返回

    int* a = (int*)malloc(sizeof(int) * 2);     //要动态内存开辟，否则失效

 

    a[0] = dog1;

    a[1] = dog2;

 

    *returnSize = 2;    //表示返回数据的多少

 

需要注意的是，内存开辟需要借助malloc，不能单纯开辟一个数组。

同时returnSize表示返回数据的多少，也需要修改

五、注意

任何数按位与 & 1，得到的结果 要么为0 要么为1。

通过 >> 右移操作符，可以遍历每一个比特位。