【位运算专题】剑指 Offer 56 – I. 数组中数字出现的次数-跟着帅地玩副业，开拓第二曲线PlayOffer

Renasc 普通 2025年1月2日下午3:07

时间复杂度O(N)，空间复杂度O(1)

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int x = 0, y = 0, z = 0, m = 1;
        // 先找到两个不同的数的异或值
        for (int socket :sockets) {
            z ^= socket;
        }

        // 找到倒数第一个不为0的值
        while ((z & m) == 0) {
            m <<= 1;
        }

        // 根据m划分为两个子数组，每个子数组都与x,y进行异或操作
        for (int socket : sockets) {
            if ((m & socket) == 0) {
                x ^= socket;
            } else {
                y ^= socket;
            }
        }
        return new int[] {x, y};
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月12日下午10:25

解题思路
– 在一组数组中有2个单独配对的数字。那么我们就需要把独配对的2个数字（a，b）分到2组里面，最后问题就转换成 1个单独的数字在数组里面，就可以用数组元素全部进行异或运算得到单独的数字了
– 数组中所有元素进行异或运算,最后得到的结果是2个单独配对数字（a，b）的异或
– 异或结果merge的二进制，哪一位为1表明从哪一位开始a和b是不同的，通过和二进制数key 1、10、100进行按位与&操作可以知晓（&结果不为0时）
– 数组所有元素 & key0来分割数组1,数组2
– 数组1和数组2各自进行全元素异或运算，得到目标的元素值
【题解1】

class Solution {
    public int[] sockCollocation(int[] sockets) {
        // 需要把单独配对的2个数字（a，b）分到2组里面

        // 数组中所有元素进行异或运算,最后得到的结果是2个单独配对数字（a，b）的异或
        int merge = 0;
        for (int i = 0; i < sockets.length; i++) {
            merge = merge ^ sockets[i];
        }

        // 异或结果merge的二进制，哪一位为1表明从哪一位开始a和b是不同的
        // 通过和 二进制数 1、10、100进行按位与&操作可以知晓
        // 【错误点】 按位与操作要括号起来(merge & key)
        int key = 1;
        while ((merge & key) == 0) {
            key = key << 1;
        }

        // 使用key的按位与是否为0来分割数组
        // 数组分割后，问题转换成1个单独元素和一群成对元素的问题
        int result1 = 0;
        int result2 = 0;
        for (int i = 0; i < sockets.length; i++) {
            if ((sockets[i] & key) == 0) {
                result1 = result1 ^ sockets[i];
            } else {
                result2 = result2 ^ sockets[i];
            }
        }
        return new int[] { result1, result2 };
    }
}

错误点1：按位与操作要括号起来(merge & key)，while ((merge & key) 0) 才是正确的

0 赞同 0 条回复

lQl 永久会员 2024年12月11日上午9:59

时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int n = 0;
        for (int num : sockets) {
            n ^= num;
        } // 遍历异或得到两数异或
        int x = 0;
        int y = 0;
        int m = 1;
        while ((n & m) == 0) {
            m <<= 1;
        }//记录两数从后往前第一个不一样的数
        for (int num : sockets) {
            if ((num & m) != 0)
                x ^= num;
            else
                y ^= num;
        }//分组异或分别得出x,y
        return new int[] { x, y };
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月10日下午10:53

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int tmp1=0;
        for(int num:sockets){
            tmp1=tmp1^num;
        }        //计算整个数组异或的结果，即x、y异或的结果
        int tmp2=1;
        while((tmp1&tmp2)==0){
            tmp2=tmp2<<1;   //找到xy异或结果第一个为1的位，也就是x和y第一个不同的位。
        }
        int x=0;
        int y=0;      //通过将sockets数组中每个数挨个与tmp2进行按位与，通过结果是否为0，将x、y进行分离。
        for(int i=0;i<sockets.length;i++){
            if((sockets[i]&tmp2)==0) x^=sockets[i];
            else y^=sockets[i];
        }
        return new int[]{x,y};
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午9:19

思路：首先对全局异或操作得到的结果即为 x^y ，通过位运算找到 x^y 第一位为1的地方diff：即 x和y第一位不相同的地方，通过该位实现对 x和y的区别，在进行异或运算，将所有diff 位相同的元素进行异或操作，由于其他元素成对出现，异或为0，最后可以得到x和y

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 即 x y 第一位不相同的位置 
            m <<= 1;
        for(int num: sockets) {           // 3. 遍历 sockets 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0 除 x 外的 元素由于成对 异或结果为0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月10日下午3:30

分组异或

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int ret=0;
        for(int n:sockets){
            ret^=n;
        }
        int div=1;
        while((div&ret)==0){
            div<<=1;
        }
        int a=0;int b=0;
        for(int n:sockets){
            if((n&div)==0) a^=n;
            else b^=n;
        }
        return new int[]{a,b};
    }
}

On o1

0 赞同 0 条回复

Aatorx 永久会员 2024年12月10日下午3:02

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        int n = 0;
        for(int num : sockets) {
            n ^= num;
        }
        int m = 1;
        while ((n & m) == 0) {
            m <<= 1;
        }
        int x = 0;
        int y = 0;
        for (int num : sockets) {
            if ((num & m) == 0) {
                x ^= num;
            }else {
                y ^= num;
            }
        }
        return {x, y};
    }
};

对数组每一个元素做亦或运算后，找到结果第一个为1的位置即为两个元素第一个不同的位置。之后按照该位置将数组分为两组，分别进行亦或运算得到结果。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

月下足迹普通 2024年12月10日上午10:50

class Solution {
public int[] sockCollocation(int[] sockets) {
//求出数组中所有数的异或结果，最后的到的是两个不同数字的异或结果
int sum = 0;
for (int i : sockets) {
sum ^= i;
}

    //找出两个不同数的二进制表示中最低位1的位置，用于划分数组
    int diff = sum & -sum;

    //划分数组
    int socket1 = 0;
    int socket2 = 0;
    for (int num : sockets) {
        if ((num & diff) == 0) {
            socket1^=num;
        }else {
            socket2^=num;
        }
    }
    int [] result = {socket1,socket2};
    return result;
}

}

0 赞同 0 条回复

苯庸普通 2024年12月10日上午9:34

class Solution {
public int[] sockCollocation(int[] sockets) {
int m = 0;
for(int x : sockets){
m ^= x;
}
int z = 1;
while((z & m) 0){
z <<= 1;
}
int i = 0, j = 0;
for(int x : sockets){
if((x & z) 0){
i ^= x;
}else{
j ^= x;
}
}
return new int[]{i, j};
}
}
思路：位运算，再找到为1的位置，根据这一位对数据分类
时间：O（n）
空间：O（1）

0 赞同 0 条回复

jaron 普通 2024年12月10日上午9:29

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int m = 0, x = 0, y = 0;
        // 全部异或起来
        for (int socket : sockets) {
            m ^= socket;
        }
        int n = 1;
        // 找出一位x y 不一样的
        while ((m & n) == 0) {
            n = n << 1;
        }
        // 根据这一位区分x y
        for (int socket : sockets) {
            if ((socket & n) == 0) {
                x ^= socket;
            } else {
                y ^= socket;
            }
        }
        return new int[] { x, y };
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年12月9日下午9:40

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int m = 1;
        int x = 0, y = 0, n = 0;
        // 1. 获取 x ^ y 的结果
        for (int socket : sockets) {
            n ^= socket;
        }

        // 2. 此时的 n = x ^ y，找到划分位置 m，直至 n & m != 0
        while ((n & m) == 0) {
            m <<= 1;
        }

        // 3. 划分为两个数组，分别计算 x、y
        for (int socket : sockets) {
            if ((socket & m) == 0) {
                x ^= socket;
            }else {
                y ^= socket;
            }
        }
        return new int[]{x, y};
    }
}

思路：位运算，将数组分为两个数组计算，每个数组都含有一个出现一次的数字。
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

晓宇普通 2024年12月9日下午8:04

class Solution {
public:
// 思路：相同的数异或得0,不同的数异或所得数至少有一位不同。先求异或所有数得z,通过z求两数的不同位所组成数；所有数和m相与，分成两组。两组分别相与就分别得到这两个不同的数。
    vector<int> sockCollocation(vector<int>& sockets) {
        if(sockets.empty()) return vector<int>();
        // 异或所有元素
        int z = 0;
        for(int i = 0;i < sockets.size();i++)
            z ^= sockets[i];

        // 求出不同元素的一位不同项
        int x = 0, y = 0, m = 1;
        while((z & m) == 0){
            m = m << 1;
        }

        // 分组异或求解
        for(int i = 0;i < sockets.size();i++){
            if(sockets[i] & m) x ^= sockets[i];
            else y ^= sockets[i];
        }

        return vector<int> {x,y};

    }
};
// o(n) o(1)

0 赞同 0 条回复

【位运算专题】剑指 Offer 56 – I. 数组中数字出现的次数

共以下 12 个回答

# 回答此问题取消回复

【位运算专题】剑指 Offer 56 – I. 数组中数字出现的次数

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复