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

=.= 普通 2024年4月5日下午4:07

class Solution {
public int[] sockCollocation(int[] sockets) {
int z = 0;
for(int i=0; i<sockets.length; i++){
z = z ^ sockets[i];
}

    int m = 1;
    while((z & m) == 0){
        m = m << 1;
    }

    int x=0, y=0;
    for(int i=0; i<sockets.length; i++){
        if((m & sockets[i]) == 0) x = x ^ sockets[i];
        else y = y ^ sockets[i];
    }

    return new int[]{x, y};
}

}
时间：O(n)
空间：O(1)

0 赞同 0 条回复

NULL 普通 2024年3月26日上午1:14

class Solution {
public int[] sockCollocation(int[] sockets) {
// 第一次遍历数组，计算数组所有元素的异或结果，得到只出现一次的两个数字的异或结果
int z = 0;
for (int i = 0; i < sockets.length; i++) {
z = z ^ sockets[i];
}

    // 找到 z 中为 1 的最低位，作为分组依据
    int m = 1;
    while ((m & z) == 0) {
        m = m << 1;
    }

    // 第二次遍历数组，根据 m 位的不同将数组分为两组，并分别对每组进行异或操作，得到只出现一次的两个数字
    int x = 0, y = 0;
    for (int i = 0; i < sockets.length; i++) {
        if ((sockets[i] & m) == 0) {
            // 数字的 m 位为 0，则归为第一组，对第一组的数字进行异或操作
            x = x ^ sockets[i];
        } else {
            // 数字的 m 位为 1，则归为第二组，对第二组的数字进行异或操作
            y = y ^ sockets[i];
        }
    }

    // 返回只出现一次的两个数字组成的数组
    return new int[]{x, y};
}

}

0 赞同 0 条回复

南梁陈庆之普通 2024年3月23日下午12:08

先计算两个不同数据的异或值，然后拆分两个数据
因为两个数据不相同，所以必存在二进制一位不等于
根据这位0或1，再遍历遍数组，找出这个位0或1情况下的异或值，此时这两个值就是不相同的值

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int sum = 0;
        for (int i = 0;i < sockets.length; i++) {
            sum ^= sockets[i];
        }
        int x =0 , y = 0;
        int m = 1;
        while ((sum & m) == 0) {
            m <<= 1;
        }
        for (int i = 0; i < sockets.length; i++) {
            if ((sockets[i] & m) != 0) {
                x ^= sockets[i];
            } else {
                y ^= sockets[i];
            }
        }
        return new int[]{x,y};
    }
}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月22日下午9:39

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int z=0;
        for(int i=0;i<sockets.length;i++){
            z=z^sockets[i];
        }

        // int m=0;
        int m=1;
        while((m&z)==0){
            m=m<<1;
        }

        int x=0;
        int y=0;
        for(int i=0;i<sockets.length;i++){
            if((sockets[i]&m)==0){ 
                x=x^sockets[i];
            }else{
                y=y^sockets[i];
            }
        }

        return new int[]{x,y};
    }
}

时间复杂度：O(n)
额外空间复杂度：O(1)
有个疑问，为什么改为 if((sockets[i]&m)1){ 会影响最后结果

0 赞同 0 条回复

一个达不刘普通 2024年3月21日下午4:59

class Solution {
public:
vector sockCollocation(vector& sockets) {
int z=0;//对所有元素进行异或，得到独立的两个数的异或结果
for(int i: sockets){
z ^= i;
}

    int m = 1;//找到二进制位不等的位置。m不能是0.会死循环，
    while((m &z) == 0){
        m <<= 1;
    }

    int x=0,y=0;
    for(int i:sockets){
        if(i & m){//分两组数据
            x ^= i;
        }else{
            y ^= i;
        }
    }

    return vector<int>{x,y};
}

};

0 赞同 0 条回复

Yox 普通 2024年3月21日上午1:32

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. 返回出现一次的数字
时间 o n 空间 o 1

0 赞同 0 条回复

神经蛙普通 2024年3月20日下午11:53

class Solution {
public:
vector sockCollocation(vector& sockets) {
int m = 1;
int n = 0;
int x = 0;
int y = 0;
for(int num : sockets)
n ^= num;
while((n & 1) 0)
{
m <<= 1;
n >>= 1;
}
for(int num : sockets ){
if(num & m ) x^= num;
else y^= num;
}
return vector{x, y};
}
};
时间复杂度 O(N)
空间复杂度 O(1)

0 赞同 0 条回复

kfaebot 普通 2024年3月20日下午9:44

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        //存储所有数的异或结果
        int res=0;
        for(int i=0;i<sockets.size();i++){
            res^=sockets[i];
        }

        //找到所有数的异或结果中最低位的1
        int tmp=1;
        while((res&tmp)==0){
            //不断左移
            tmp=tmp<<1;
        }

        //分组做异或
        int a=0;
        int b=0;
        for(int i=0;i<sockets.size();i++){
            if((sockets[i]&tmp)==0){
                a^=sockets[i];
            }
            else{
                b^=sockets[i];
            }
        }
        return {a,b};
    }
};

0 赞同 0 条回复

言之命至普通 2024年3月20日下午9:18

1.对所有数字进行一次异或，得到只出现一次的数字的异或值
2.找出x和y第一个不相同的二进制位，从右开始数，从x^y的结果可知，右边出现的第一个1，就是不相同的二进制位
3. 把 nums 划分成两个子数组，让 nums 各数与m & 运算，则x和y一定分别位于两个子数组中。 m位为0的一组，为1的一组，x和y一定分别位于两组，各组除了x和y，其他元素异或为0，最后只剩x，y。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int z = 0;
        for(int i = 0;i < nums.length; i++){// 得到x^y
            z = z ^ nums[i];
        }

        int m = 1;
        while((m & z) == 0){// 找出x和y第一个不相同的二进制位，从右开始数，从x^y的结果可知，右边出现的第一个1，就是不相同的二进制位
        // m中那个1的位置就是第一个不同的二进制位
            m = m << 1;
        }
        // 把sockets划分成两个子数组，让sockets各数与m & 运算，则x和y一定分别位于两个子数组中

        int x = 0, y = 0;
        // m位为0的一组，为1的一组，x和y一定分别位于两组，各组除了x和y，其他元素异或为0，最后只剩x，y。
        for(int i = 0;i < nums.length; i++){
            if((nums[i] & m) == 0){
                //结果为 0 的子数组，一边统计用异或统计x
                x = x ^ nums[i];
            } else {
                //结果为 1 的子数组，一边统计用异或统计y
                y = y ^ nums[i];
            }
        }

        return new int[]{x, y};
    }
}

0 赞同 0 条回复

Jimmy 普通 2024年3月20日下午7:48

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

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        int z = 0;
        //把所有元素相异或会得到两个单身元素异或的结果
        for(int i=0;i<sockets.size();i++){
            z ^= sockets[i];
        }
        //找这两个单身元素究竟是在二进制的哪个位上出现不一样
        int m = 1;
        while((m & z) == 0){
            m = m<<1;
        }

        int x = 0;
        int y = 0;
        //用m与数组中的每个元素相与，其结果要么为1要么为0，这样可以把整个数组分成两波，而且两个单身元素被分开了
        for(int i=0;i<sockets.size();i++){

            if((m & sockets[i]) == 0){
                x ^= sockets[i];//相异或，得到一个单身元素
            }else{
                y ^= sockets[i];
            }
        }
        return {x,y};
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月20日下午5:31

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int ret = 0;
        for(int n:sockets){
            ret = ret^n;    //对所有数字进行一次异或，得到只出现一次的数字的异或值
        }
        int div = 1;    //一个分析器，帮忙在异或结果中找到任意为1的位
        while((div&ret) == 0){
            div <<= 1;
        }
        int a = 0, b = 0;
        for(int n:sockets){
            if((div&n) != 0){
                a^=n;
            } else {
                b^=n;
            }
        }
        return new int[]{a,b};
    }
}

0 赞同 0 条回复

云无深雁影普通 2024年3月20日下午2:24

class Solution {
public int[] sockCollocation(int[] sockets) {
int temp = 0;
for(int i = 0; i <sockets.length; i++){
temp ^= sockets[i];
}
//此时temp为两数的异或
int m = 1;
while((temp & m) 0){ m <<= 1;}
int x = 0;
int y = 0;
for(int i = 0; i <sockets.length; i++){
if((sockets[i] & m) 0){ x ^= sockets[i];}
else y ^= sockets[i];
}
return new int[] {x,y};

}
//时间复杂度On 空间复杂度O1

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月20日上午8:21

打卡

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        // 得到x^y
        int z = 0;
        for(int i = 0; i < sockets.size(); i++) {
            z ^= sockets[i];
        }

        // 找出x和y第一个不相同的二进制位，从右开始数，从x^y的结果可知，右边出现的第一个1，就是不相同的二进制位
        // m中那个1的位置就是第一个不同的二进制位
        int m = 1;
        while((m & z) == 0) {
            m = m << 1;
        }
        // 把sockets划分成两个子数组，让sockets各数与m & 运算，则x和y一定分别位于两个子数组中
        int x = 0, y = 0;
        // m位为0的一组，为1的一组，x和y一定分别位于两组，各组除了x和y，其他元素异或为0，最后只剩x，y。
        for(int i = 0; i < sockets.size(); i++) {
            if((sockets[i] & m) == 0) {
                x ^= sockets[i];
            } else {
                y ^= sockets[i];
            }
        }
        return {x, y};
    }
};

0 赞同 0 条回复

紫芝普通 2024年3月19日下午11:22

思路：主要的一个思想是：在所有元素进行异或后得到x^y，只需要找到x^y的任意一个1，然后再进行分组异或

“`c++
class Solution {
public:
vector sockCollocation(vector& sockets) {
int tmp = 0;
for (int i=0; i{x, y};
}
};
“`

0 赞同 0 条回复

MARS 普通 2024年3月19日下午10:58

/**
 * @param {number[]} sockets
 * @return {number[]}
 */
var sockCollocation = function (sockets) {
    let x = 0
    for (let i = 0; i < sockets.length; i++) {
        x = x ^ sockets[i]   //得到 a^b  
    }
    let y = 1

    while ((y & x) == 0)   //获得分解
        y <<= 1;
    let a=0,b=0

    for(let n of sockets){
        if(y&n){
            a^=n
        }else{
            b^=n
        }
    }
    return [a,b]
};

0 赞同 0 条回复

王位詮釋普通 2024年3月19日下午10:08

哈希表：
class Solution {
    public int[] sockCollocation(int[] sockets) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<sockets.length;i++){
            if(map.containsKey(sockets[i])){
                int temp = map.get(sockets[i]);
                map.put(sockets[i],++temp);
                continue;
            }
            map.put(sockets[i],1);
        }
        int[] result = new int[2];
        int count = 0;
        for(Integer i:map.keySet()){
            if(count>1){
                break;
            }
            if(map.get(i)==1){
                result[count++] = i;
            }
        }
        return result;
    }
}
位运算：
class Solution {
    public int[] sockCollocation(int[] sockets) {
        int m = 0;
        for(int i=0;i<sockets.length;i++){
            m = m^sockets[i];
        }
        int a = 1;//寻找不同数字的哪一位是不同
        while((m&a)==0){
            a = a << 1;//一直找到某一位不相同为止
        }
        int x = 0;
        int y = 0;
        for(int i = 0;i<sockets.length;i++){
            if((sockets[i] & a)==0){
                x = x^ sockets[i];
            }else{
                y = y^sockets[i];
            }
        }
        return new int[]{x,y};
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月19日下午9:10

class Solution {
public:
    vector<int> sockCollocation(vector<int>& sockets) {
        int z = 0;
        for(auto const & i : sockets){
            z = z ^ i;
        }

        // 寻找x与y不同的那位
        int m = 1;
        while((m & z) == 0){
            m = m << 1;
        }


        int x = 0;
        int y = 0;
        for(auto const & i : sockets){
            // 分成两个子数组
            if((m & i) == 0){
                x = x ^ i;
            }else{
                y = y ^ i;
            }
        }
        return vector<int>{x, y};

    }
};

0 赞同 0 条回复

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

共以下 17 个回答

# 回答此问题取消回复

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

共以下 17 个回答

# 回答此问题 取消回复

# 回答此问题取消回复