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

Gg 普通 2023年4月30日上午1:24

class Solution {
    // 时间为O(n)、空间O（1）
    public int singleNumber(int[] nums) {
        // 用一个数组来记录num中 每一位1的和
        int[] count = new int[32];
        for(int i = 0; i < nums.length; i ++){
            // 累计int中每一位的1
            for(int j = 0; j < 32; j ++){
                count[j] += nums[i] & 1;
                nums[i] >>>= 1;
            }
        }
        // 还原count数组成数字, 对3进行取模，得到的余数，为该数在位的值
        int res = 0;
        for(int i = 0; i < 32; i++){
            res <<= 1;
            res |= (count[31 - i] % 3);
        }
        return res;
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月16日下午7:08

位运算解决

class Solution {
    public int singleNumber(int[] nums) {
        //相同数字，每个位上的元素都是一样的，所以统计数字对3取余就可以了。
        int res = 0;
        int m = 1;
        for(int i = 0; i < 32; i++){
            int sum = 0;
            for(int j = 0; j < nums.length; j++){
                if((nums[j] & m) != 0){
                    sum++;
                }
            }
            res = res + m * (sum % 3);
            m = m << 1;
        }
        return res;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月10日下午3:32

def singleNumber(nums):
    m = 1
    res = 0
    for bit in range(32):
        bit_res = 0
        # 得到所有元素这一位数字的和
        for _ in nums:
            # 说明这一位上的数为1，如果这一位的数为0，&的结果就是0
            if _ & m != 0:
                bit_res += 1
        # 直接将这一位转换为十进制
        res = res + m*(bit_res % 3)

        m = m << 1


    return res

0 赞同 0 条回复

lucca 普通 2023年1月9日上午10:29

哈希

class Solution {
    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                cnt[i] += (num & 1);
                num >>= 1;
            }
        }

        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            ans <<= 1;
            if (cnt[i] % 3 != 0) ans++;
        }
        return ans;
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月2日下午4:18

func singleNumber(nums []int) int {
    //哈希表计算个数
    num := map[int] int{}
    for _, vlaue := range nums{
        num[vlaue]++ //统计个数
    }
    //重新遍历找到只出现一次的那个数返回
    for key, value := range num{
        if value == 1{
            return key
        }
    }
    return 0
}

0 赞同 0 条回复

庄重普通 2022年11月26日下午7:16

// 思路：
//     1.列出数组中所有数的二进制形式
//     2.每一列二进制的综合并对3取余，会得到那个只出现一次的数的二进制位数
//     3.进行循环，并把得到的二进制数据还原成十进制
//     4.使用状态机可以有少的时间复杂度
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bit[32] = {};

        long m = 1;
        int sum = 0;

        for(int i = 0; i < 32; ++i){
            for(int j = 0;j < nums.size(); ++j){
                if((nums[j] & m) != 0){
                    bit[i]++;
                }
            }
            //3的倍数，取余后只会出现0 / 1 两种情况
            bit[i] %= 3;
            sum = sum + m * bit[i];
            //防止出现位数越界，使用long类型
            m = m << 1;
        }

        return sum;
    }
};
//时间复杂度O(n)
//空间复杂度O(1)

0 赞同 0 条回复

xye 普通 2022年11月24日下午3:49

func singleNumber(nums []int) int {
    var count [32]int
    res := 0
    for i := 0; i < 32; i++ {
        count[i] = 0
    }
    m := 1
    for i := 0; i < 32; i++ {
        for j := 0; j < len(nums); j++ {
            //不能用==1的原因是，当m左移之后与运算的结果就不是1了
            if nums[j] & m != 0 {
                count[i]++
            }
        }
        count[i] %= 3 
        res += count[i] * m
        m <<= 1 
    }
    return res
}

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

0 赞同 0 条回复

yanshuojune 普通 2022年11月20日下午11:14

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

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 位运算
        temp = 1
        res = [0 for i in range(32)]
        sum = 0
        for i in range(32):
            for j in nums:
                # 将所有元素表示程二进制之后，每个位的值{0，1}相加，
                if j & temp != 0:
                    res[i] += 1
            # 再除3取余（%），为0表示出现一次对应位置为0，为1表示对应位置为1
            res[i] %= 3
            # 将结果转为10进制
            sum += res[i] * temp
            # temp左移一位
            temp <<= 1            
        return sum

0 赞同 0 条回复

鸿渐普通 2022年11月15日下午10:40

 int [] k = new int[32];
        for (int num : nums) {
            //从低位开始，将每一位都加起来
            for (int j = 0; j < 32; j++) {
                k[j] += (num >> j & 1) == 1 ? 1 : 0;
            }
        }
        int res = 0;
        for(int i = 31;i>=0;i--){
            //从高位开始一位一位比较
            res = res << 1;
            if(k[i]%3 == 1){
                //或上1的作用就是既可以保持原来的位的数字，但是又可以改变
                //想要改变的位
                res = (res | 1);
            }
        }
        return res;

0 赞同 0 条回复

小肸永久会员 2022年11月15日下午7:32

思路一：如果一个数出现了三次，那么各个二进制位出现的次数都是3的倍数。只需统计每一个二进制位上出现的次数，对3取余，然后将剩下的求和就是只出现一次的数。时间复杂度O(32 * N)，空间复杂度O(1)。

class Solution {
    public int singleNumber(int[] nums) {
        int[] bit = new int[32];
        int res = 0;
        int tag = 1;
        for (int i = 0; i < 32; i ++) {
            for (int j = 0; j < nums.length; j ++) {
                if ((tag & nums[j]) != 0) {
                    bit[i] ++;
                }
            }
            bit[i] %= 3;
            res = res + bit[i] * tag;
            tag = tag << 1;
        }
        return res;
    }
}

思路二: 用一个哈希表存储<数字，次数>。时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

你有点可爱喔普通 2022年11月15日上午9:59

我是傻子

class Solution {
    public int singleNumber(int[] nums) {
        //位运算;出现次数最少的
        int  [] num = new int[32];
        int m = 1;
        int sum = 0;
        //这里的i是说明int 类型的数值是32位，从而在做与运算的时候像下一位移动
        for (int i = 0;i <32;i++){
            for (int j = 0;j<nums.length;j++){
                if((nums[j] & m) != 0){
                    num[i]++;
                }
            }
            //取模，数组中有数据出现了三次
            num[i] = num[i]%3;
            //求出这个数据的十进制
            sum=sum+ num[i]*m;
            m = m<<1;
        }
      return sum;

    }
}

0 赞同 0 条回复

y 普通 2022年11月14日下午9:41

var singleNumber = function(nums) {
   let res = 0;
   for (let i = 0; i < 32; i++) {
       let count = 0;
      for (let j = 0; j < nums.length; j++) {
         if ((nums[j] >> i & 1) == 1) {
             count++;
         }
      }

      if(count % 3 != 0) {
          res = res | 1 << i;
      }
   }
  return res;
};

想不到

0 赞同 0 条回复

天然普通 2022年11月12日下午12:46

脑袋只剩下统计了，位运算这个实在是想不到，时间复杂度O(n)空间复杂度O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones,twos = 0,0
        for num in nums:
            ones = ones^num&~twos
            twos = twos^num&~ones
        return ones

0 赞同 0 条回复

派大星普通 2022年11月11日下午9:51

class Solution {
//时间复杂度O(n)
//空间复杂度O(1)
    public int singleNumber(int[] nums) {
        //找到求得二进制数上的每一位，对3取余然后把每一位组合起来最终形成只出现一次的数
        int[] num = new int[32];
        int a = 1;
        int value = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.length; j++) {
                if((nums[j] & a) != 0){
                    num[i]++;
                }
            }
            //因为除了目的数其他数都为三个，确定这一位上有没有该数
            int tem = num[i] % 3;
            //累加得到数
            value += tem * a;
            a <<= 1;
        }
        return value;
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月11日下午2:13

妙哉

class Solution {
    public int singleNumber(int[] nums) {
        int[] t = new int[32];
        int m = 1;
        int sum = 0;
        for(int i = 0; i < 32; i++) {
            for(int j = 0; j < nums.length; j++) {
                if((nums[j] & m) != 0) {
                    t[i]++;
                }
            }
            t[i] %= 3;
            sum += t[i]*m;
            m <<= 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

T 普通 2022年11月10日下午9:12

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        // 循环遍历每个数，统计二进制每位的数量
        for(int num : nums) {
            for(int i = 0; i < 32; i++) {
                counts[i] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0;
        // %3得到只出现一次的数的二进制倒序, 用或运算反向还原数
        for(int j = 0; j < 32; j++) {
            int tmp = counts[31 - j] % 3;
            res <<= 1;
            res |= tmp;
        }
        return res;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年11月10日下午5:00

class Solution {
    public int singleNumber(int[] nums) {
        int[] res= new int[32];
        int m = 1;
        int sum = 0;
        for(int i=0;i<32;i++){
            for(int j =0;j<nums.length;j++){
                if((nums[j]&m) != 0){
                    res[i]++;
                }
            }
            res[i] = res[i]%3;
            sum = sum+res[i]*m;
            m = m<<1;
        }
        return sum;
    }
}

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

0 赞同 0 条回复

追普通 2022年11月10日下午2:10

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sum = 0;
        vector<int> res(32);  //需要指定数组的大小
        unsigned int m = 1;   //可能出现左移最高位为符号位，因此需要将m设置为无符号数
        for(int i = 0; i < 32; i++){  //位数的循环
            for(int j = 0; j < nums.size(); j++){  //数组中数的循环
                if((nums[j] & m) != 0)  
                     res[i]++;
            }
            res[i] = res[i] % 3;
            sum += res[i] * m;
            m = m << 1;
        }
        return sum;
    }
};

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月10日下午2:00

时间复杂度为O（n），空间复杂度为O（1）

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32];
        int m = 1;
        int sum = 0;
        for(int i = 0;i < 32;i++){
            for(int j = 0;j < nums.length;j++){
                if((nums[j] & m) != 0){
                    res[i]++;
                }
            }
            res[i] = res[i] % 3;
            sum = sum + res[i]*m;
            m = m << 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

just 普通 2022年11月10日下午12:50

//bit运算
class Solution {
public:
int singleNumber(vector& nums) {
int res[32]={0};
for(int cur:nums){
for(int i=0;i<32;++i){
if((cur&(1<<i))) res[i]++;
}
}
for(int i=0;i<32;++i) res[i]%=3;
int ret=0;
for(int i=0;i<32;++i){
if(res[i]) ret+=(1<<i);
}
return ret;
}
};

0 赞同 0 条回复

是梦终空永久会员 2022年11月10日上午11:12

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

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];//\记录所有数字的各二进制位的 1 的出现次数
        for(int n : nums){                      //循环遍历数组
            for(int i = 0;i<32;i++){
                count[i] = count[i]+(n & 1);    //更新数组i位  (n+1)可得到最右一位的数
                n = n>>1;                       //i位->i+1位
            }
        }
        int res = 0,m = 3;                      //m是出现次数，res是结果
        for(int i = 0;i<32;i++){
            res = res<<1;                       //左移，为了恢复到10进制
            res = res | count[31-i]%m;          //得到右侧一位数该是多少
        }
        return res;
    }
}

0 赞同 0 条回复

So 普通 2022年11月10日上午9:29

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32];
        int m = 1;
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.length; j++) {
                if ((nums[j] & m) != 0) {
                    res[i]++;
                }
            }
            res[i] %= 3;
            sum = sum + res[i] * m;
            m = m << 1;
        }
        return sum;
    }
}

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

0 赞同 0 条回复

青木普通 2022年11月10日上午12:39

/**
    有点难理解，用two 和 one 保存余数的个数，
    总之 
    00 表示能被3整除，说明答案中这一位为0
    01 表示3余1，说明答案中这一位为1
    10 表示3余2，由于题目中数量不是3就是1，因此之后还有一个，会循环

    因此 two one 就表示了各个位上的1数量余3，最后的one就代表答案

    这个过程确实写得太简练了

 */

class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for(int num : nums){
            // 当two为0，如果num为1，则one为1，否则不变
            // 当two为1，无论怎样，  one为0
            one = (one ^ num) & ~two;
            // 当one为0，如果two为1，则two为0（说明one已经加过1了，two需要升级）
            // 当one为1，无论怎样，  two为0  （说明one可以加1，two保持0就可以）
            two = (two ^ num) & ~one;
        }
        return one;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月9日下午11:32

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

/**
一个数字出现三次，那么对应的二进制的每一位都出现三次
如果把出现三次的二进制加起来，那么每一位都能被三整除
此时加入出现一次的
对于出现一次的
每一位能被三整除对应--->0
每一位不能被三整除对应--->1
 */
class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for(int i = 0;i < nums.length;i++){
            for(int j = 0;j < 32;j++){
                count[j] += (nums[i]>>j & 1) == 1 ? 1 : 0;//判断当前位是不是为1
            }
        }
        int res = 0;
        for(int i = 31;i >= 0;i--){
            res = res << 1;
            if(count[i] % 3 == 1){
                //说明res该位为1
                res |= 1;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月9日下午11:09

class Solution {
    public int singleNumber(int[] nums) {
        //直接统计每一位上的1有多少 最后除3有余数的一定是target产生的
        int[] res = new int[32];
        int m = 1;
        int sum = 0;
        for(int i = 0; i < 32; i++){
            for(int num: nums){
                //判断某个数的某一位上是否为1 
                if((num & m) != 0){
                    res[i]++;
                }
            }
            res[i] = res[i] % 3;
            sum = sum + res[i] * m;
            m <<= 1;
        }
        return sum;
       
       //方法二 直接用hashmap
        HashMap map = new HashMap();
        for(int num: nums){
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(int key: map.keySet()){
            if(map.get(key) == 1){
                return key;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月9日下午10:47

统计+重组数字，这种解法适用于任何“其他数字出现m次，其中一个只出现1次的题目”吗，但是个人感觉需要注意int有的机器上不止32位
最后一个python为什么这样求负数没想明白

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        bits=[0]*32
        for x in nums:
            for i in range(0,32,1):
                bits[i]=bits[i]+(x&1)
                x=x>>1
        num=0
        for i in range(31,-1,-1):
            num=(num<<1)|(bits[i]%3)
        if bits[31]==0:
            return num
        else:
            return ~(num ^ 0xffffffff)  # 为什么这里是这样求得，没想明白

0 赞同 0 条回复

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

共以下 26 个回答

哈希

# 回答此问题取消回复

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

共以下 26 个回答

哈希

# 回答此问题 取消回复

# 回答此问题取消回复