当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
154 30

共以下 30 个回答

  • Gg 普通 2023年4月23日 下午11:23 
    class Solution {

    public int[] singleNumbers(int[] nums) {
        // 当只有一个数不存在重复数时，利用异或计算，全部数进行一次，最后一个剩下来的就是不重复的
        // 当存在两个数不重复时，最后的数就是两个数的异或
        int sum = 0;
        for(int num : nums){
            sum ^= num;
        }
        // 选取最后的数中最后一位为1的数。代表该位置存在两个数不相同
        int div = 1;
        while( (sum&div) == 0){
            // 不断最移动
            div <<= 1;
        }
        // 将选取出来的数和每一个数进行异或，为0的成一组、为1的成一组。则两组中分别有一个不同数
        int x = 0, y = 0;
        for(int n : nums){
            if((div & n) != 0){
                x ^= n;
            }else{
                y ^= n;
            }
        }
        return new int[]{x,y};


    }
}
    0 赞同 0 条回复
  • 宁 永久会员 2023年3月16日 下午5:55

    找到可以区分的位置

    class Solution {
    public int[] singleNumbers(int[] nums) {
        //找出哪一位不同，用哪一位区分这个数组
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            res ^= nums[i];
        }
        int diff = 0;
        for(int i = 0; i < 32; i++){
            if((res & (1 << i)) != 0){
                diff = 1 << i;
                break;
            }
        }
        int temp1 = 0;
        int temp2 = 0;
        for(int i = 0; i < nums.length; i++){
            if((nums[i] & diff) != 0){
                temp1 ^= nums[i];
            }else{
                temp2 ^= nums[i];
            }
        }
        return new int[]{temp1, temp2};
    }
}
    0 赞同 0 条回复
  • PatNick 普通 2023年1月10日 下午2:45 
    def singleNumbers(nums):
    all = 0
    # 将整个数组进行异或，得到那两个不重复数字的异或结果
    for _ in nums:
       all = all ^ _


    # 寻找异或结果中最后边的第一个1
    m = 1
    while all & m == 0:
        m = m << 1


    # 根据这个值将原数组的元素分为两部分
    x = 0
    y = 0
    for __ in nums:
        if m & __ == 0 :
            x = x ^ __
        else:
            y = y ^ __

    return [x,y]
    0 赞同 0 条回复
  • lucca 普通 2023年1月9日 上午10:16

    取异或和，找到任意为1的位，代表两个数在这一位不同，必然一个是0，一个是1，只要对该位是0的数和该位是1的数分组求异或和即可 （第一次见这种做法，秀）

    class Solution {
    public int[] singleNumbers(int[] nums) {
        int sum = 0;
        for (int num : nums) sum ^= num;

        int m = sum & -sum;
        int a = 0, b = 0;
        for (int num : nums) {
            if ((num & m) == 0) a ^= num;
            else b ^= num;
        }
        return new int[]{a, b};
    }
}
    0 赞同 0 条回复
  • symbol 普通 2022年12月2日 下午4:03 
    func singleNumbers(nums []int) []int {
    var a int
    for i := range nums{
        a ^= nums[i] // 对数组中的所有元素进行异或
    }
    mask := a & (-a) //二进制位最右边一位为1的数字
    res := make([]int,2)
    for _,v :=range nums{
        if (v & mask) == 0{
            res[0] ^= v
        }else{
            res[1] ^= v
        }
    }
    return res
}
    0 赞同 0 条回复
  • 🚲南下 普通 2022年12月2日 下午1:58 
    class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);
        for(int i = 2; i <= n;i++){//i<=n，动态规划
            int curmax = 0;
            for(int j = 1; j < i; j++){
                int tempmax = max((i-j)*j, j*dp[i-j]);
                curmax = max(curmax,tempmax); //转移方程
            }
            dp[i] = curmax;
        }
        return dp[n];
    }
};
    0 赞同 0 条回复
  • 庄重 普通 2022年11月26日 下午6:46 
    // 思路：
//     1. 讲数组中的所有元素进行异或操作，得到出现一次的数的异或值
//     2.找到两个值二进制低位到高位第一个不一样的位
//     3.根据m将nums分到两个子数组中
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = 0;

        //讲数组中的所有元素进行异或操作，得到出现一次的数的异或值
        for(int i = 0; i < nums.size(); ++i){
            n ^= nums[i];
        }        
        //此时 n 的值只有不相等的位数才为1
        //找到两个值二进制低位到高位第一个不一样的位,即为m的值
        int m = 1;//0000 0001
        while((m & n) == 0){//
            m <<= 1;//左移
        }

        //根据m将nums分到两个子数组中
        int x = 0, y = 0;
        for(int i = 0; i < nums.size(); ++i){
            if((nums[i] & m) == 0){
                x ^= nums[i];
            }
            else{//(nums[i] & m) == 1
                y ^= nums[i];
            }
        }

        return vector<int>{x,y};
    }
};
//时间复杂度O(n)
//空间复杂度O(1)
    0 赞同 0 条回复
  • xye 普通 2022年11月24日 下午3:13 
    func singleNumbers(nums []int) []int {
    //res := []int{}
    m := 1
    x := 0
    for _, num := range nums {
        x = x ^ num
    }
    for m & x == 0 {
        m = m << 1
    }
    a, b := 0, 0
    for _, num := range nums {
        if m & num != 0 {
            a = a ^ num
        }else{
            b = b ^ num
        }
    }
    return []int{a, b}
}

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

    0 赞同 0 条回复
  • 刺猬 普通 2022年11月24日 下午12:29 
    class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        if(nums.size() == 2)    return nums;
        int ret = 0;
        for (int n : nums)
            ret = ret ^ n;
        int div = 1;
        while ((div & ret) == 0)
            div = div << 1;
        int a = 0, b = 0;
        for (int n : nums)
            if (div & n)
                a = a ^ n;
            else
                b = b ^ n;
        return vector<int>{a, b};
    }
};

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

    0 赞同 0 条回复
  • yanshuojune 普通 2022年11月20日 下午10:33

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

    class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        # 位运算：所有元素做位运算得到不相等的两元素x ^ y
        from functools import reduce
        Xor = reduce(lambda x,y:x^y, nums)
        # Xor中为1的位置表示x和y不相等的位置，找到第一个不相等的位置
        temp = 1
        while Xor & temp == 0:
            # 左移一位
            temp <<= 1
        # 对nums中元素进线分组，相同元素放进同一组，x，y放入不同组，并对两组做异或
        x, y = 0, 0
        for i in nums:
            if i & temp == 0:
                x ^= i
            else:
                y ^= i
        # 返回结果
        return [x, y]
    0 赞同 0 条回复
  • 鸿渐 普通 2022年11月15日 下午10:04 
    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};
    }
}
    0 赞同 0 条回复
  • Whatever 永久会员 2022年11月15日 下午8:13

    时间O(n)，空间O(1)

    class Solution {
    public int[] singleNumbers(int[] nums) {
        //所有元素异或的结果
        int res = 0;
        for(int i = 0;i < nums.length; i++){
            res = res ^ nums[i];
        }
        //寻找不为1的最低位
        int m = 1;
        while((m & res) == 0){
            m = m << 1;
        }

        int x = 0, y = 0;
        //与m相与为0 分入组1 ，否则分入组2
        //使得两个只出现一次的元素分入不同组，且相同元素均分入同一组，最终得到x,y
        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 条回复
  • 小肸 永久会员 2022年11月15日 下午6:50

    思路：利用两个相同的数异或值为0的特点可以在一个只有一个数字出现一次，其它数字出现两次的数组中找到这个数字。怎么在这个数组中找到只有两个数字出现一次的这两个数字，想办法分组，找到这个数字最右边异或位为1的这一位，创建一个变量，这个变量除了这一位为1，其它位都为0，再利用这个数和&操作进行分组。时间复杂度O(N)，空间复杂度O(1)。

    class Solution {
    public int[] singleNumbers(int[] nums) {
        int allXOR = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            allXOR ^= nums[i];
        }
        // tag记录两个值最右边不相等的一位，即异或位为1的位
        int tag = 1;
        while ((tag & allXOR) == 0) {
            tag = tag << 1;
        }
        int x = 0, y = 0;
        for (int i = 0; i < nums.length; i ++) {
            if ((nums[i] & tag) == 0) {
                x ^= nums[i];
            } else {
                y ^= nums[i];
            }
        }
        return new int[]{x, y};
    }
}
    0 赞同 0 条回复
  • @ 普通 2022年11月15日 上午11:05

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

    class Solution {
    public int[] singleNumbers(int[] 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) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }
}
    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年11月13日 下午4:51 
    class Solution {
    public int[] singleNumbers(int[] nums) {
        // 异或运算
        int sum = 0;
        //所有的数进行异或操作
        for(int num:nums){
            sum^=num; 
        }
        int m = 1;

        while((m&sum)==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 条回复
  • 天然 普通 2022年11月11日 下午11:12

    先找两个^起来的结果n，然后通过分离器，确定两个数的位置，再继续异或
    时间复杂度O(n) 空间复杂度O(1)

    class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        n,x,y,m=0,0,0,1
        cur = []
        for i in range(len(nums)):
            n ^= nums[i]
        while n&m ==0:
            m<<=1
        for num in nums:
            if num&m : x ^=num
            else: y ^=num 
        return y,x
    0 赞同 0 条回复
  • 派大星 普通 2022年11月11日 下午9:13 
    class Solution {
//把数组拆解成两个数组来异或
//时间复杂度O(n)
//空间复杂度O(1)
    public int[] singleNumbers(int[] nums) {
        int[] values = new int[2];
        int tem = 0;
        //将数组中的每一个元素都异或一遍获取数组中两个不同的数字的异或结果
        for (int i = 0; i < nums.length; i++) {
            tem = tem ^ nums[i];
        }
        //因为异或是相同为0，相反为1,找到tem中从右数的第一个1
        int t = 1;
        while((tem & t) == 0){
            t <<= 1;
        }
        //找到从右数的第一个第一个不同后，然后从数组中找到该位置是1和0的数分别异或
        int x = 0,y = 0;
        for (int i = 0; i < nums.length; i++) {
            if((nums[i] & t)==0){
               x = x ^ nums[i]; 
            }else {
                y = y ^ nums[i];
            }
        }
        values[0] = y;
        values[1] = x;
        return values;
    }
}
    0 赞同 0 条回复
  • 易水寒 永久会员 2022年11月11日 下午1:49

    与运算和异或运算

    class Solution {
    public int[] singleNumbers(int[] nums) {
        int tmp = 0;
        for(int num : nums) {
            tmp ^= num;
        }
        int m = 1;
        while((tmp&m) == 0) {
            m <<= 1;
        }
        int x = 0;
        int y = 0;
        for(int num : nums) {
            if((num & m) == 0) {
                x ^= num;
            }
            else {
                y ^= num;
            }
        }
        return new int[] {x, y};
    }
}
    0 赞同 0 条回复
  • y 普通 2022年11月11日 上午9:32 
    //通过异或
//a ^ a = 0, 
//  0 ^ a = a
//  b ^ a ^ b = b ^ b ^ a = 0 ^ a = a
var singleNumbers = function(nums) {
   let num = 0;
   for(let i of nums) {
       num ^= i;
   }
   let cur = 1;
   while((cur & num) == 0) {
       cur <<= 1;
   }

   let a= 0, b = 0;
   for(let i of nums) {
       if((i & cur) == 0) {
           a ^= i;
       } else {
           b ^= i;
       }
   }
   return [a,b];
};
    0 赞同 0 条回复
  • T 普通 2022年11月10日 下午6:18 
    class Solution {
    public int[] singleNumbers(int[] nums) {
        int s = 0, a = 0, b = 0, m = 1;
        // 通过异或，得到数组中不重复数a和b的异或 s = a ^ b
        for(int num : nums) {
            s ^= num;
        }

        // 通过和m做 与 操作， 得到s二进制从右往左最近的1
        while((s & m) == 0) {
            m <<= 1;
        }

        // 再根据a,b二进制位不同且最右来进行分组
        for(int num : nums) {
            if((num & m) != 0) a ^= num;
            else b ^= num;
        }
        return new int[]{a, b};
    }
}
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2022年11月10日 下午3:50 
    class Solution {
    public int[] singleNumbers(int[] nums) {
        int z =0;
        for(int num:nums){
            z ^= num;
        }
        int m =1;
        while((m&z)==0){
             m=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 条回复
  • just 普通 2022年11月10日 下午12:13

    //分组异或
    class Solution {
    public:
    vector singleNumbers(vector& nums) {
    int ret=0,tar=1;;
    for(int cur:nums) ret^=cur;
    while((ret&tar)0) tar=tar<<1;
    int a=0,b=0;
    for(int cur:nums){
    if(cur&tar) a^=cur;
    else b^=cur;
    }
    return{a,b};

    }

    };

    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月10日 上午11:58

    时间复杂度为O（n），空间复杂度为O（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((nums[i] & m) == 0){
                x = x ^ nums[i];
            }else{
                y = y ^ nums[i];
            }
        }
        int[] result = new int[2];
        result[0] = x;
        result[1] = y;
        return result;
    }
}
    0 赞同 0 条回复
  • 追 普通 2022年11月10日 上午10:33 
    class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int z = 0;
        for(int num : nums)
            z ^= num;
        int m = 1;
        while((m & z) == 0) m <<= 1;  // 找到z中最右边的一个1，使用这个1来对数组中的数进行分组
        int x = 0, y = 0;
        for(int num : nums){
            if((m & num) == 0) x ^= num;  // 0与上任何数都为0，因此相与之后的数组只在m为1的那一位上有区别（0或1）
            else y ^= num;
        }
        return vector<int> {x, y};  //返回数组的语法
    }
};
    0 赞同 0 条回复
  • So 普通 2022年11月10日 上午9:19 
    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) {
                x = x ^ nums[i];
            } else {
                y = y ^ nums[i];
            }
        }
        return new int[]{x, y};
    }
}

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

    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年11月9日 下午11:21

    太难了

    /**
异或运算性质：
交换律、结合律((a^b)^c == a^(b^c))
对任何数x,都有 x ^ x = 0,x ^ 0 = x
自反性 A^B^B = A --> A^B=C 则 C^B=A
 */
class Solution {
    //假设结果数为A B
    public int[] singleNumbers(int[] nums) {
        int x = 0;//用于记录A B 的异或结果
        //得到A^B的结果
         for(int val : nums){
             x ^= val;
        }
        //x & (-x) 本身的作用是得到最低位的1 如6=(00000110) -6(11111010)补码
        int flag = x & (-x);
        /**
        而我们所需要的做到的是：利用这个1来进行分组，也就是做到将A和B区分开
        前面已经知道，x是我们需要的结果数A和B相异或的结果，也就是说，x的二进制串上的任何一个1，都能成为区分A和B的条件
        因此我们只需要得到x上的任意一个1，就可以做到将A和B区分开来
         */
        int res = 0;//用于记录A或B中其中一者
        //分组操作
        for(int val : nums){
            /**
            根据二进制上的1进行分组
            需要注意的是，分组的结果必然是相同的数在相同的组，且还有一个结果数
            因此每组的数再与res=0一路异或下去，最终会得到那个结果数A或B
            且由于异或运算具有自反性，因此只需得到其中一个数即可
             */
            if((flag & val) != 0){//等于0的是最低位不为1的A/B
                res ^= val;
            }
        }
        return new int[]{res,x ^ res};
    }
}
    0 赞同 0 条回复
  • 是梦终空 永久会员 2022年11月9日 下午11:04

    这题真想了挺久……
    时间O(n)
    空间O(1)

    class Solution {
    public int[] singleNumbers(int[] nums) {
        // z = x ^ y
        int z = 0;
        int len = nums.length;
        for(int i = 0;i<len;i++){
            z = z ^ nums[i];
        }
    // 找到一个数来判断x.y的最底位不同的数
        int m =1;
        while((m&z) == 0){
            m = m<<1;
        }
    // 相同的数和m异或结果肯定相同，而且结果只能为1，m因为是上面有条件得到的，所以xy与m异或结果肯定不同,这样就可以分为两个数组
        int x= 0;
        int y = 0;
        for(int i = 0;i<len;i++){
            if((nums[i]&m) == 0){
                x = x^nums[i];
            }
            else{
                y = y^nums[i];
            }
        }
        return new int[]{x,y};
    }
}
    0 赞同 0 条回复
  • lobort 普通 2022年11月9日 下午10:47 
    class Solution {
    public int[] singleNumbers(int[] nums) {
        int two = 0, m = 1, x = 0, y = 0;
        for(int num: nums){
            two ^= num;  //two是两个不相等的数异或的结果 
        }
        //two二进制位上为1 的时候代表 两个不相等的数在这位上也不相等
        while((two & m) == 0){
            m <<= 1;
        }
        for(int num: nums){
            if((num & m) == 0){
                x ^= num;
            }else{
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}
    0 赞同 0 条回复
  • 青木 普通 2022年11月9日 下午10:22 
    /**
    确实很妙，全部异或后得mul取最低位的1，把所有遍历的数最低位的1位置和mul相同的分成一组，
    如果两个数相同则最低位也相同，因此分组后的异或值就是答案

    时间O(n)
    空间O(1)
 */

class Solution {
    public int[] singleNumbers(int[] nums) {
        int mul = 0;
        int del = 1;
        int one = 0;
        int two = 0;
        for(int num : nums){
            mul ^= num; 
        }
        while((mul & del) == 0){
            del = del << 1;
        }
        for(int num:nums){
            if((num & del) == 0){
                one ^= num;
            }
            else{
                two ^= num;
            }
        }
        return new int[]{one, two};
    }
}
    0 赞同 0 条回复
  • 黎昕 普通 2022年11月9日 下午9:13

    思路：异或+标记（分组）
    1. 某一个位为0或者1可以将一大堆数分开来
    2. 有相同的两个数异或为0
    3. 异或运算支持交换律与结合律
    4. 所以可以通过全部异或一遍得到 两个不同数的异或值
    5. 这个异或结果中为1的位代表两个数的那一位也不相同，可以凭借其中一位将他们分开
    6. 挑选一个异或值为1的位，将数组分成两个，一个异或结果是a，一个异或结果是b

    class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        sum=0
        for x in nums:
            sum=sum^x
        a,b=0,0
        i=0
        while True: # 得到最低非0位
            if (sum&1)==1:
                break
            else:
                sum=sum>>1
                i+=1
        tmp=1<<i
        for x in nums:
            if (x&tmp)==0:
                a=a^x
            else:
                b=b^x
        return [a,b]
    0 赞同 0 条回复

# 回答此问题

后才能回答