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

Sheng 永久会员 2023年9月11日下午9:52

看的答案

        int result = 0;
        for(int num : nums) {
            result = result ^ num;
        }

        //到这里还是两个不同的数x  y   异或的结果
        //找到结果中是1的最低位，如果结果是010100，那么找到的结果100
        //因为1存在的地方，一定是x  y 二进制上不一样的地方
        int z = 1;
        while((result & z) == 0) {
            z = z << 1;
        }

        //根据这个特性就能把数组分为两部分，x在一部分，y在一部分
        //最后就转化为，”数组中有一个数出现一次，其他都是出现两次“ 的问题
        int x = 0;
        int y = 0;
        for(int num : nums) {
            if((num & z) == 0) {
                x = x ^ num;//x在一部分
            }
            else {
                y = y ^ num;//y在一部分
            }

        }
        int [] kk =  {x, y};
        return  kk;

0 赞同 0 条回复

小肸永久会员 2023年9月6日上午11:15

class Solution {
    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int i : nums) {
            res ^= i;
        }
        //通过baseVal进行分组
        int baseVal = 1;
        while (res % 2 != 1) {
            baseVal = baseVal << 1;
            res /= 2;
        }
        List<Integer> aGroup = new ArrayList<>(nums.length);
        List<Integer> bGroup = new ArrayList<>(nums.length);
        for (int i : nums) {
            if ((baseVal & i) == 0) {
                aGroup.add(i);
            } else {
                bGroup.add(i);
            }
        }
        //下面两次遍历有些冗余
        int a = 0;
        for (int i : aGroup) {
            a ^= i;
        }
        int b = 0;
        for (int i : bGroup) {
            b ^= i;
        }
        return new int[]{a, b};
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月5日下午1:57

思路：借助异或运算找出只出现一次的数，这里有两个数，所以可以将数组分为两个，各自包含只出现一次的数，找到后返回。
复杂度：时间复杂度O(N)，空间复杂度O(1)

class Solution {
    public int[] singleNumbers(int[] nums) {
        int z = 0;// 遍历^运算，得到两个数的异或结果z，z等于1的位置肯定是两数不相同的位置
        for (int num : nums) {
            z = z ^ num;
        }
        int m = 1;// 循环左移，找到两数从右往左第一个不相同的位置
        while ((z & m) == 0) {
            m <<= 1;
        }
        int x = 0;
        int y = 0;// 遍历数组，&计算不为0分到x组，为0分到y组，xy组异或分别得到两个数
        for (int num : nums) {
            if ((num & m) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

0 赞同 0 条回复

c 普通 2023年8月31日下午7:39

相同数字异或为0，异或+分组

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = nums[0];
        for(int i = 1;i<nums.length;i++){
            x^=nums[i];
        }
        int j = 0;
        while((x&(1<<j))==0){
            j++;
        }
        int[] res = new int[2];
        for(int i = 0;i<nums.length;i++){
            if((nums[i]&(1<<j))==0){
                res[0]^=nums[i];
            }else{
                res[1]^=nums[i];
            }
        }
        return res;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月31日上午12:04

记录一下这题，用到异或。如果没要求空间复杂度为O(1)，可以使用哈希表

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums){
            n ^= num;
        }
        while((n & m) == 0){
            m <<= 1;
        }
        for(int num : nums){
            if((num & m) != 0){
                x ^= num;
            }else{
                y ^= num;
            }
        }
        return new int[] {x, y};
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月30日下午11:39

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

        int m = 1;
        //找到z中最右边的1
        while ((m & z) == 0) {
            m = m << 1;
        }

        int x = 0, y = 0;

        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & m) == 0) {
                // 结果为0的子数组，进行异或
                x = x ^ nums[i];
            } else {
                // 结果为1的子数组，进行异或
                y = y ^ nums[i];
            }
        }

        return new int[]{x,y};


    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月30日下午10:28

/ 根据标志位区分，时间复杂度O(n)
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int val1 = 0;
        for(int i=0;i<nums.size();++i)
        {
            val1 ^= nums[i];
        }
        int tmp =1;
        while((tmp&val1)==0)
        {
            tmp<<=1;
        }
        int x=0,y=0;
        for(int i=0;i<nums.size();++i)
        {
            if((tmp&nums[i])==0)
            {
                x^=nums[i];
            }
            else y^=nums[i];
        }
        return {x,y};
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月30日下午3:10

位运算的运用
之前就知道异或可以找到在成对数列里面只出现一次的情况，不过这里还需要更进一部思考有两个只出现一次的情况下异或结果也是有意义的：异或为1的位表示这两个数在这一位是不同的，由此可以将数据分成两部分，每一个部分找到只出现一次的数就可以了

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int result { 0 };
        for (auto& n : nums) {
            result ^= n;
        }
        int i = 1;
        while (!(result & i)) {
            i <<= 1;
        }
        int a { 0 };
        int b { 0 };
        for (auto& n : nums) {
            if (n & i) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return {a, b};
    }
};

0 赞同 0 条回复

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

共以下 8 个回答

# 回答此问题取消回复

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复