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

June 普通 2023年8月27日下午4:29

class Solution {
public int[] singleNumbers(int[] nums) {
int[] ans = new int[2];
int tmp = nums[0];
for (int i=1 ; i < nums.length ; i++) {
tmp = tmp ^ nums[i];
}
int index = 0;
int num = tmp;
while(num!=0) {
int a = num & 1;
if (a 1)
{
break;
}
num = num >> 1;
index ++;
}
// 找到异或值不同的位
int ans1 = tmp;
int ans2 = tmp;
//分组异或
for (int i=0;i<nums.length;i++) {
int a = (nums[i] >> index) & 1;
if (a 1)
{
ans1 ^= nums[i];
}else{
ans2 ^= nums[i];
}
}
ans[0] = ans1;
ans[1] = ans2;
return ans;
}
}

0 赞同 0 条回复

hi 普通 2023年8月17日上午9:39

异或操作
第一次异或找出两个数的异或值，找到该值某位数上为1 的位数（因为是异或得到的1，证明两个数该位上的值不相等）
循环所有数，判断该位上是否为1，一样的再次异或，以此把两个数分开

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum = 0;
        for(int x : nums) sum ^= x;

        int k = 0;
        while(!(sum >> k & 1)) k++;

        int first = 0;
        for(int x : nums)
            if(x >> k & 1) first ^= x;

        return vector<int>{first, sum ^ first};
    }
};

0 赞同 0 条回复

艺普通 2023年8月4日下午3:57

“`c++
class Solution {
public:
vector singleNumbers(vector& nums) {
int z=0;
int i;
for(i=0;i{x, y};
}
};

0 赞同 0 条回复

普通 2023年8月2日上午12:08

c++ 代码位运算的运用
class Solution {
public:
vector singleNumbers(vector& nums)
{ int no=0,x=0,y=0,m=1;
for(int i=0;i<nums.size();i++)
no^=nums[i];
while(!(no & m)) // 2. 循环左移，计算 m
m <<= 1;
for(int i=0;i<nums.size();i++)
{
if(nums[i]&m) x^=nums[i];
else
y^=nums[i];
}
return vector{x,y};

};

0 赞同 0 条回复

CaCO3 永久会员 2023年8月1日下午8:31

”’java
class Solution {
public int[] singleNumbers(int[] nums) {
int ret = 0;
for(int n : nums){
ret ^= n;
}
int div = 1;
while((div & ret) 0){
div <<=1;
}
int a=0,b=0;
//找出不一样的二进制位，相同的数还是被分到同一组
//最后遍历异或
for(int n:nums){
if((div & n) != 0){
a ^= n;
}else{
b ^= n;
}
}
return new int[]{a,b};
}
}
”’
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

北辰普通 2023年8月1日下午3:54

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

思路：通过位运算找到不相同的两个数的从右往左数不同位，然后利用这个数将这两个数分开，然后得到两个子数组，虽然这两个数组的元素个数不确定，但是相同元素可定被分到同一组，这样两个数组直接进行异或得到的还是各自数组中只出现一次那个数

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月30日下午7:48

class Solution {
    public int[] singleNumbers(int[] nums) {
        int z = 0;
        for(int i=0;i<nums.length;i++){
            z ^= nums[i];
        }
        // 此时 z = x^y
        // 从右向左遍历，找到第一位1
        int m = 1;
        while((z&m)==0){
            // 循环左移，计算m
            m<<=1;
        }
        // 将数组分成两个子数组,分别循环异或
        int x =0;
        int y=0;
        for(int num: nums){
            // m位置==1
            if((num&m)!=0) x ^=num;
            // m位置==0
            else y^=num;
        }
        return new int[]{x,y};
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

Mby 普通 2023年7月29日下午9:59

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;
        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 = x ^ nums[i];
            }else{
                //结果为1的子数组，用异或统计y
                y = y ^ nums[i];
            }
        }
        return new int[] {x,y};
        //时间复杂度： O(n)
        //空间复杂度： O(1)
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年7月28日下午5:52

class Solution {
public int[] singleNumbers(int[] nums) {
//经典与或的场景
int a =nums[0];
for(int i=1;i<nums.length;i++)
{
a=a^nums[i];
}
//a = num1 ^ num2;
//把a分成两部分因为 num1 和num2 两数不同一定有一位二进制
// a & 0001 a&00010 选择m 不停左移
int m =1;
while((a&m)0)
{
m<<=1;
}
//此时 m能表示哪一位 num1 num2 里面不相同的位置
int x=0;
int y=0;
for(int i=0;i<nums.length;i++)
{
if((nums[i]&m)0)
{
x=x^nums[i];
}else
{
y=y^nums[i];
}
}
int [] result=new int[]{x,y};
return result;
}
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月27日下午1:15

class Solution {
    public int[] singleNumbers(int[] nums) {
        // 输入：nums = [4,1,4,6]
        //输出：[1,6] 或 [6,1]
        int[] res = new int[2];
        // 先异或把2个不一样的数字异或结果搞出来
        int temp = 0;
        for (int i = 0; i < nums.length; i++) {
            temp = temp ^ nums[i];
        }
        int index = 1;
        // 把不同的数字分放在2组，这样就能异或找到他，2个不同的数字异或位必定至少有1位不同，找到这个位置，然后分2组异或即可
        while ((temp & index) == 0) {
            index = index << 1;
        }
        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((index & nums[i])==0) {
                a = a ^ nums[i];
            } else {
                b = b ^ nums[i];
            }
        }
        res[0] = a;
        res[1] = b;
        return res;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月26日下午11:47

7.25
Day17：下面是代码

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年7月26日下午9:23

代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int x:nums){
            if(set.contains(x)){
                set.remove(x);
                continue;
            }
            set.add(x);
        }
        int[] arr = new int[2];
        int i=0;
        for(int y:set){
            arr[i++] = y;
        }
        return arr;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月26日下午7:37

没接触过根本想不到啊，主要是异或操作，另外找到第一个不同位置然后将数组分成两组的操作也很巧妙。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int z = 0;
        for(int i = 0;i < nums.size();++i){
            z ^= nums[i];
        }
        int m = 1;
        while((m & z) == 0){
            m = m << 1;
        }
        int x = 0,y = 0;
        for(int i = 0;i < nums.size();++i){
            if((nums[i] & m) == 0){
                x ^= nums[i];
            }
            else{
                y ^= nums[i];
            }
        }
        return vector<int>{x,y};
    }
};

0 赞同 0 条回复

CKX 普通 2023年7月26日下午5:09

func singleNumbers(nums []int) []int {
    //将数字分为两组，独特数字不同组，相同为一组

    //a^b的结果
    res := 0
    //a，b两数为出现一次的数字
    a, b := 0, 0
    for _, v := range nums {
        res ^= v
    }

    index := 0
    for res & 1 == 0 {
        index +=1
        res >>= 1
    }
    for _, v := range nums {
        if (v >> index) & 1 == 0 {
            a ^= v
        } else {
            b ^= v
        }
    }
    return []int{a, b}

}

0 赞同 0 条回复

Luminous 普通 2023年7月25日下午11:09

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

0 赞同 0 条回复

#00456B 普通 2023年7月25日下午8:52

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        /*
        整个算法的流程比较复杂
        1. 所有的数字进行异或，会得到结果z。这个z是两个只出现一次的数字x和y的异或的结果
        2. 求得第n个二进制位不相同。
            e.g. x = 1000
                 y = 0110
                 --------
                 z = 1110
            这个时候需要用一个不断向左移位的1来相与得到第n个二进制位不相同。
                 n = 0010
        3. 用这个n去对原来的数组进行相与，是肯定能把x和y分到两个子问题中去的。
            此时问题就变成了数组中数字只出现一次的两个子问题
            然后对x和y分别进行异或
        */
        int z = 0; // x ^ 0 = x
        for(int num:nums){
            z ^= num;
        }

        int n = 1;
        while((z & n) == 0){
            n <<= 1;
        }
        int x = 0;
        int y = 0;
        for(int num:nums){
            cout<< (num & n) <<endl;
            if((num & n) == 0){//(num & n)得有括号，不然优先级不如==
                x ^= num;

            }
            else{
                y ^= num;
            }
        }
        return {x,y};
    }
};

0 赞同 0 条回复

AD钙奶普通 2023年7月25日下午4:46

没怎么做过，有点难住了，看题解弄懂了。
分组异或

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xorRes = 0;
        for(int num : nums) {
            xorRes ^= num;
        }
        int lowbit = 1;
        while((xorRes & lowbit) == 0) {
            lowbit <<= 1;
        }
        int ans1 = 0, ans2 = 0;
        for(int num : nums) {
            if((num & lowbit) != 0) {
                ans1 ^= num;
            } else {
                ans2 ^= num;
            }
        }
        return new int[] {ans1, ans2};
    }
}

0 赞同 0 条回复

阿尚普通 2023年7月25日下午3:15

class Solution {
    public int[] singleNumbers(int[] nums) {

        int n = 0;
        for(int num : nums){
            n ^= num;//假设出现一次的两个数字为a,b，则n = a ^ b
        }

        int lastOne = n & ((~n) + 1);//获取最后一个一
        int a = 0;
        for(int num : nums){
            if((num & lastOne) != 0) a ^= num; 
        }

        return new int[]{a, (n ^ a)};
    }
}

0 赞同 0 条回复

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

共以下 18 个回答

# 回答此问题取消回复

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

共以下 18 个回答

# 回答此问题 取消回复

# 回答此问题取消回复