九号球普通 2023年11月20日下午11:18

“`java
//分组异或
class Solution {
public int[] sockCollocation(int[] sockets) {
int ret = 0;
for (int i = 0; i < sockets.length; i++) { ret = (ret^sockets[i]); } int div = 1; while ((ret & div) == 0) { div <<= 1; } int a = 0; int b = 0; for (int i = 0; i < sockets.length; i++) { if ((sockets[i] & div) != 0) { a ^= sockets[i]; } else { b ^= sockets[i]; } } return new int[]{a,b}; } }

0 赞同 0 条回复

招舟子普通 2023年9月2日上午12:27

class Solution {
public int[] singleNumbers(int[] nums) {
int t=0;
for(int i=0;i<nums.length;i++){
t = t^nums[i];
}
int a = 1;
while((a&t)0){
a= a<<1;
}
int x=0,y=0;
for(int i=0;i<nums.length;i++){
if((a&nums[i])0){
x=x^nums[i];
}else{
y= y^nums[i];
}
}
return new int[]{x,y};
}
}
加油

0 赞同 0 条回复

jhfuture 普通 2023年8月24日下午9:29

“`java
public int[] singleNumbers(int[] nums) {

        // 利用异或，两个相同的异或为0
        // 为什么这里初始值为0，因为初始值为0和任何值异或的结果都是原来的值
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum=sum^nums[i];
        }
        // 两个怎么处理，一分为二，使用两个数组
        // 怎么划分？使用他们最小的一个差异1，然后对数组进行与操作
        // 那两个数字于的结果不同。为什么使用1，因为就是要找出第一个1

        int m=1;
        while((sum & m)==0){
            // 一直指导找到那个最小位置上的1
            m=m<<1;
        }
    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 条回复

彦，，# 普通 2023年8月4日下午2:54

分成两组
 vector<int> singleNumbers(vector<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) x ^= num;
            else y ^= num;
        }
        return vector<int> {x,y};
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:53

“`C++
vector findSingleNumbers(vector& nums) {
int xorResult = 0;
// Step 1: 获取两个只出现一次的数字的异或结果
for (int num : nums) {
xorResult ^= num;
}

// Step 2: 找到异或结果中为1的位，用于将数组划分为两个子数组
int mask = 1;
while ((xorResult & mask) == 0) {
    mask <<= 1;
}

int num1 = 0, num2 = 0;
// Step 3: 将原数组划分为两个子数组，并分别异或运算得到两个只出现一次的数字
for (int num : nums) {
    if ((num & mask) == 0) {
        num1 ^= num;
    } else {
        num2 ^= num;
    }
}

return {num1, num2};

}

“`

0 赞同 0 条回复

憨憨永久会员 2023年7月17日下午4:46

通过位运算加上分组的形式，来计算出数值
时间O(n)
空间O(1)

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

0 赞同 0 条回复

江畅普通 2023年7月16日上午12:14

// 数组中数字出现的次数
// 时间复杂度 O(N)
// 空间复杂度 O(1)
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0; // 只出现一次的数字
        int y = 0; // 只出现一次的数字

        int n = 0; // 存储 nums 各元素异或结果, 即为 x^y
        int m = 1;

        // nums 各元素异或结果, 即为 x^y
        for (int num : nums) {
            n = n ^ num;
        }

        // eg. x = 1 = 0001
        //     y = 6 = 1010
        // n = x ^ y = 1011
        // m & n     = 0001, m = 0001
        while ((m & n) == 0) {
            m = m << 1;
        }

        for (int num : nums) {
            if (num & m) {
                x = x ^ num;
            }
            else {
                y = y ^ num;
            }
        }
        return vector<int>{x, y};
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月15日上午9:48

java
class Solution {
    public int[] singleNumbers(int[] nums) {
    /*
    思路：1.先对所有元素进行异或 2.将异或结果与0001/0010/0100等进行与，
    结果为0则与序列中1所在的位在异或中是相等的
    3.找到不相等的位之后，再与数组元素相与，此时两个只出现一个的元素可以分开，再全部异或
     */

        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((m & nums[i]) == 0) {
                x = x ^ nums[i];
            } else {
                y = y ^ nums[i];
            }
        }
        return new int[]{x, y};
    }
}

时间复杂度是o(n), 空间复杂度是o(1)

0 赞同 0 条回复

花老爷普通 2023年7月14日下午6:57

位运算
时间：O(n)
空间：O(1)

class Solution {
    public int[] singleNumbers(int[] nums) {
        int mod = 0;
        for(int num: nums) {
            mod ^= num;
        }
        int firstOne = 1;
        while ((firstOne & mod) == 0) {
            firstOne <<= 1;
        }
        int a = 0, b = 0;
        for (int num: nums) {
            if ((firstOne & num) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月14日上午11:07

【思路】将整个数组异或后得到的结果即为x^y，此时再利用异或结果将数组分为两个子集（分别包含x和y），分别对两个子集进行异或即可得到x和y
【复杂度】时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int all_xor = 0;
        for (auto &n: nums) all_xor ^= n;

        int mask = 1;
        while(!(all_xor & mask)) mask <<= 1;

        int x = 0, y = 0;
        for (auto &n: nums) {
            if (n & mask) x ^= n;
            else y ^= n;
        }

        return {x, y};
    }
};

0 赞同 0 条回复

Jerry 普通 2023年7月9日下午10:34

 // 位运算：异或+左移+与
class Solution {
    public int[] singleNumbers(int[] nums) {
        int target1 = 0, target2 = 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) {
                target1 ^= num; 
            } else {
                target2 ^= num;
            }
        }
        return new int[] {target1 , target2}; //返回 两个只出现一次的数字
    }
}

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

0 赞同 0 条回复

WhyNot 普通 2023年7月9日下午7:13

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    int z=0;
  for(int i=0;i<numsSize;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<numsSize;i++)
  {
      if(m&nums[i])
      {
          x=x^nums[i];
      }
      else
     {
       y=y^nums[i];
     }
  } 
    *returnSize=2;
    int* ret =(int*)malloc(sizeof(int) * 2);
    ret[0] = x;
    ret[1] = y;

    return ret;
}

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

0 赞同 0 条回复

伏月三十普通 2023年7月8日上午10:54

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;
        int y=0;
        for(int i=0;i<nums.length;i++){
            if((m&nums[i])==0){
                //分成两个子数组
                x=x^nums[i];
            }else{
                y=y^nums[i];
            }
        }
        return new int[]{x,y};
    }
}

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

0 赞同 0 条回复

Vow the vow。普通 2023年7月8日上午10:24

要求找到两个数字，因此需要进行分组异或。

public int[] singleNumbers(int[] nums) {
        int res = 0;
        for(int num : nums){
            res ^= num;
        }
        int div = (res & (res-1) ^ res);
        // while((div & res) == 0){  
        //     div <<= 1;
        // }

        int a = 0, b = 0;
        for(int num : nums){
            if((num & div) != 0){  
                a ^= num;
            }else{
                b ^= num;
            }
        }
        return new int[]{a,b};
    }

0 赞同 0 条回复

局外人普通 2023年7月8日上午8:38

思路：根据异或的性质，将所有数组中的数字一起异或后，最终剩下两个数组异或的结果，且两数字二进制位不同的位的异或结果必然为1。因此，从右向左，找到第一个为1的位置，将数组分为两个部分，分别异或，便可以得到这两个数字
时间复杂度：O(n) 空间复杂度：O(1)

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xor = 0;
        for(int n:nums){
            xor ^= n;
        }

        int sep = 1;
        while((xor & sep)==0){
            sep <<= 1;
        }

        int a=0, b=0;
        for(int x:nums){
            if((x & sep) != 0)      a ^= x;
            else                        b ^= x;
        }

        return new int[]{a, b};

    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年7月7日下午10:19

// 时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int num = 0;
        for(int i =0;i<nums.size();++i)
        {
            num^=nums[i];
        }
        //cout<<num<<endl;
        int m = 1;
        while((m&num) == 0)
        {
            m <<= 1;
        }
        //cout<<m<<endl;
        int x = 0, y =0;
        for(int i =0;i<nums.size();++i)
        {
            if((m&nums[i])==0) // ==的优先级比 &高，需要括号
            {
                x^=nums[i];
            }
            else
            {
                y^=nums[i];
            }
        }
        //cout<< x<<" "<<y<<endl;
        return vector<int>{x,y};
    }
};

0 赞同 0 条回复

硬核洋葱普通 2023年7月7日下午10:05

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < 32; ++i){
            int bitnum = 0;
            for(auto n : nums)
                if(n >> i & 1)
                    bitnum += 1;
            ans |= (bitnum % 3) << i;
        }
        return ans;
    }
};

int 一共32位，一位位检查，模三
时间复杂度 O(n) 空间复杂度 O(1)

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月7日下午8:39

懂了但没全懂
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    public int[] singleNumbers(int[] nums) {
        // 相同数异或结果为0， 某数跟0异或的结果为它本身。
        // 求出不同的两个数异或的结果
        int z = 0;
        for(int i = 0; i < nums.length; i++){
            z = z ^ nums[i];
        }

        // 求第几个二进制位不同（取最右的）
        int m = 1;
        while((z & m) == 0){
            m = m << 1;
        }

        // 分成两组：等于m和不等于m的
        int x = 0, y = 0;
        for (int i = 0; i < nums.length; i++){
            if((nums[i] & m) == 0) {
                x = x ^ nums[i];
            } else {
                y = y ^ nums[i];
            }
        }

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

0 赞同 0 条回复

张开怀普通 2023年7月7日下午8:10

class Solution{
public:
       vector<int> singleNumbers(vector<int>& nums){
              int z = 0;
              // 全部元素取异或
              for(int i=0; i< nums.size(); i++){
                     z = z ^ nums[i];
              }
              int m=1;
              // 找出区分x，y的进制位
              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){
                             // 结果为 0 的子数组，一边用异或统计 x
                             x = x ^ nums[i];
                      }else {
                             // 结果为 1 的子数组，一边用异或统计 y
                            y = y ^ nums[i];
                      }
              }
              return vector<int>{x,y};
       }
};

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

0 赞同 0 条回复

Yodl. 普通 2023年7月7日下午7:40

//根据 X^Y 中的 1 位对原数组进行分组
//时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    vector singleNumbers(vector& nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)         // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)         // 2. 循环左移，计算 m
            m <<= 1;
        for(int num : nums) {       // 3. 遍历 nums 分组
            if(num & m) x ^= num;   // 4. 当 num & m != 0
            else y ^= num;          // 4. 当 num & m == 0
        }
        return vector {x, y};  // 5. 返回出现一次的数字
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月7日下午5:59

MY

根据 X^Y 中的 1 位进行分组

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月7日下午3:44

//思路:找出能分别x 和 y 的二进制位，将x 和 y分开，分别做两组异或
//时间O(n) 空间O(1)
public int[] singleNumbers(int[] nums) {
        int x = nums[0];
        for(int i = 1;i < nums.length;i++){
            x = x ^ nums[i];
        }

        //此时 x = x ^ y;
        //找到能区分x 和 y 的位置
        int bit = 1;
        while((x & bit) == 0){  //等于0（相同）就看下一位
            bit = bit << 1;
        }

        int[] result = new int[2];
        for(int i = 0;i < nums.length;i++){
            if((nums[i] & bit) == 0){
                result[0] = result[0] ^ nums[i];
            }else{
                result[1] = result[1] ^ nums[i];
            }
        }
        return result;

    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月7日下午3:39

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        for i in range(len(nums)):
            res = res ^ nums[i]

        m = 1
        while m & res == 0:
            m = m << 1

        x, y = 0, 0

        for i in range(len(nums)):
            if nums[i] & m == 0:
                x = x ^ nums[i]
            else:
                y = y ^ nums[i]

        return [x, y]

时间复杂度为O(n)

0 赞同 0 条回复

Ming 普通 2023年7月7日下午2:37

由于空间复杂度是O(1)，考虑位运算
先得到所有数组异或的值，双数出现的数字会抵消，剩下两个不同的数字的异或值，
确定z的第一个1的位置从右到左，，再循环数组，分辨遇见第一个1做与运算是0或者是1，可得出这两个数，其他数字因为出现两次会被抵消

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((z & m) == 0) {
            m = m << 1;
        }
        int x = 0, y = 0;
        for(int i = 0; i < nums.length; i++) {
            if((m & nums[i]) == 0) {
                x = x^nums[i];
            } else {
                y = y^nums[i];
            }
        }
        return new int[]{x,y};
    }
}

0 赞同 0 条回复

小吕普通 2023年7月7日下午2:12

c++实现，看过题解，是一个比较巧妙的思路
vector singleNumbers(vector& nums) {
int len = nums.size();
int sum = 0;
for(int i =0;i<len;i++)
{
sum ^=nums[i];
}
int div = 1;
while((div&sum)0)
{
div<<=1;
}
int a=0,b= 0;
for(int n:nums)
{
if(div&n)
{
a^=n;
}
else b^=n;
}
return vector{a,b};
}

0 赞同 0 条回复

yxy 普通 2023年7月7日下午1:46

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for(auto y: nums)
            x^=y;
        int pos = 0;
        while(x)
        {
            if(x&1==1)
                break;
            pos++;
            x>>=1;
        }
        int res1 = 0, res2 = 0;
        for(auto y: nums)
        {
            if((y>>pos)&1==1)
                res1^=y;
            else
                res2^=y;
        }
        return {res1, res2};
    }
};

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

0 赞同 0 条回复

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

共以下 26 个回答

MY

# 回答此问题取消回复

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

共以下 26 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复