九号球普通 2023年11月21日下午8:40

“`java
class Solution {
public int trainingPlan(int[] actions) {
//存放每一位1的个数
int[] count = new int[32];
int sum = 0;
int m = 1;
for (int i = 0; i < 32; i++) { for (int action : actions) { if ((action & m) != 0){ count[i]++; } } sum += count[i] % 3 * m; m <<= 1; } return sum; } }

0 赞同 0 条回复

招舟子普通 2023年9月2日上午1:03

class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int c = 1;
if(map.containsKey(nums[i])){
c++;
map.replace(nums[i],c);
continue;
}
map.put(nums[i],c);
}
for (Integer i : map.keySet()) {
if(map.get(i)1){
return i;
}
}
return 0;
}
}
直接map

0 赞同 0 条回复

jhfuture 普通 2023年8月24日下午10:02

“`java
空间复杂度为 O(1)，时间复杂度为 O（n）
class Solution {
public int singleNumber(int[] nums) {
// 定义一个32位的数组，数组的每一位储存对应数组每个数的二进制的1的个数，最后将每一位余3，然后再将这个数组翻译成数字即可。】
int[] arrar=new int[32];
int sum=0;
int m=1;
for(int i=0;i<32;i++){
for(int j=0;j>1;
}
// 每一次统计完后处理
arrar[i]=arrar[i]%3;
// 怎么转换呢？实际上是二进制转10进制的过程，每次加上
// 二进制位数 * 2^n
sum=sum+ m*arrar[i];
m= m<<1;

    }

    return sum;


}

}

0 赞同 0 条回复

彦，，# 普通 2023年8月4日下午3:22

位运算
int res = 0;
        for (int i = 0, sub = 0; i < 32; ++i, sub = 0) {
            for (auto &n : nums) sub += ((n >> i) & 1);
            if (sub % 3) res |= (1 << i);
        }
        return res;

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:24

“`C++
int singleNumber(vector& nums) {
vector count(32); // 统计各个位上出现的次数

// 统计每个数字的每一位出现的次数
for (int num : nums) {
    for (int i = 0; i < 32; ++i) {
        count[i] += (num & 1);
        num >>= 1;
    }
}

int result = 0;
// 对每一位的出现次数取余，得到只出现一次的数字
for (int i = 0; i < 32; ++i) {
    result |= (count[i] % 3) << i;
}

return result;

}

“`

0 赞同 0 条回复

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

一样的思路，代码不太一样
时间 O（N）
空间 O （1）

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32];
        for(int i = 0;i< nums.length ;i++){
            int a = nums[i];
            int id=0;
            while(a > 0){
                if((a & 1) == 1){
                    res[id]++;
                }
                id++;
                a = a>>1;
            }
        }
        int ans=0;
        int num = 1;
        for(int i=0;i<32;i++){
            if(res[i]%3==1){
                ans += num;
            }
            num = num << 1;
        }
        return ans;
    }
}

0 赞同 0 条回复

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

// 数组中出现的数字2
// 时间复杂度 O(N)
// 空间复杂度 O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int>  count(32, 0);
        unsigned int m = 1;
        int          res = 0;
        for (int i = 0; i < 32; ++i) {
            for (int num : nums) {
                if ((num & m) != 0) {
                    ++count[i];
                }
            }
            count[i] %= 3;
            res += count[i] * m;
            m = m << 1;
        }
        return res;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月15日上午11:08

java
class Solution {
    public int singleNumber(int[] nums) {
        /* 根据评论题解采用状态机的方法，位对3取余后有0,1,2三种状态，分别是00,01,10
           nums[i]的某一位是1时，进位00->01->10->00.... 是0时则状态不变 用two one表示状态机
           如何进行进位：
           if two = 0:
              if nums[i] = 0:
                one = one
              if nums[i] = 1:
                one = ~one
           if two = 1:
              if nums[i] = 0:
                one = 0
              if nums[i] = 1:
                one = 0
            则ones = one ^ nums[i] & ~two，twos也是同理，从而得出状态机的状态，注意到此题two的状态
            只为0，只用考虑one的状态
        */
        int one = 0;
        int two = 0; //初始状态为00
        for(int i = 0; i < nums.length; i++) {
            one = one ^ nums[i] & ~two;
            two = two ^ nums[i] & ~one;
        }
        return one;
    }
}

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

0 赞同 0 条回复

花老爷普通 2023年7月14日下午8:36

哈希表
时间：O(n)
空间：O(n)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            if (map.getOrDefault(num, 0) != 0) {
                if (map.get(num) == -1) {
                    continue;
                }
                map.put(num, -1);
            } else {
                map.put(num, 1);
            }
        }
        for(int key: map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

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

【思路】针对int的每一位进行统计，最后%3来判断result该位是否为1
【复杂度】时间复杂度O(n)，空间复杂度O(1)

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

0 赞同 0 条回复

屠龙手段普通 2023年7月11日下午8:32

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

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a[31] = {0};
        int m = 1;
        int res = 0;
        // 32位
        for(int i = 0; i < sizeof(a)/sizeof(a[0]); i++){
            // 按位求和
            for(int j = 0; j < nums.size(); j++){
                if((nums[j] & m) != 0) a[i]++;
            }
            // 对每位模3，得到多出来的一位
            a[i] %= 3;
            res += a[i] * m;
            // 左移一位
            m = m << 1;
        }
        return res;
    }
};

状态机时间复杂度O(n) 空间复杂度O(1)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for(int i = 0; i < nums.size(); i++){
            one = one ^ nums[i] & ~two;
            two = two ^ nums[i] & ~one;
        }
        return one;
    }
};

0 赞同 0 条回复

伏月三十普通 2023年7月8日上午11:30

“`javaclass Solution {
public int singleNumber(int[] nums) {
int[] array=new int[32];
int m=1; //同时控制与数组元素相与和将将最终结果转成十进制
int sum=0;
for(int i=0;i<32;i++){
for(int j=0;jarray[i]=array[i]%3; sum=sum+array[i]*m;//把每一位转成10进制加起来 m=m<<1; } return sum; }

}

“`

0 赞同 0 条回复

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

遍历每一位，取统计与3取余后不为0的位，即为出现一次的数字。

public int singleNumber(int[] nums) {
        int[] count = new int[32];
        int res = 0;
        int mask = 1;
        for(int i = 0; i < 32; i++){
            for(int num : nums){
                if((num & mask) != 0){
                    count[i]++;
                }
            }
            res += (count[i] % 3) * mask;
            mask <<= 1;
        }
        return res;
    }

0 赞同 0 条回复

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

思路：统计所有数字中，在int整型的32位中每一位出现的次数，将每一位出现的次数-3，余下的便是出现一次的次数的二进制位，将二进制位转换成十进制数字即可
时间复杂度：O(n) 空间复杂度：O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int[] bit = new int[32];
        int off = 1;
        int sum=0;

        for(int i=0; i<32; i++){
            for(int n:nums){
                if((n&off)!=0)  bit[i]++;
            }

            bit[i] = bit[i]%3;
            sum += bit[i]*off;
            off <<= 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月7日下午11:39

时间复杂度O(n)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i=31;i>=0;i--)
        {
            int count=0;
            for(auto& x: nums)
            {
                if((x>>i&1)==1)
                    count++;
            }
            res*=2;
            if(count%3==1)
                res+=1;
        }
        return res;
    }
};

0 赞同 0 条回复

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

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:52

这题不会，看完讲解也不会😓

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 条回复

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

class Solution{
public:
       int singleNumber(vector<int>& nums){
              vector<int> res(32,0);
              unsigned int 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){
                                   res[i]++;
                            }
                     }
                     res[i]%=3;
                     m<<=1;
              }
              return sum;
       }
}

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

0 赞同 0 条回复

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

//对于出现三次的数字，各二进制位出现的次数都是 3 的倍数
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0, sub = 0; i < 32; ++i, sub = 0) {
            for (auto &n : nums) sub += ((n >> i) & 1);
            if (sub % 3) res |= (1 << i);
        }
        return res;
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月7日下午6:04

MY

对于出现三次的数字，各二进制位出现的次数都是 3 的倍数

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

0 赞同 0 条回复

Ming 普通 2023年7月7日下午5:36

出现三次的数字化为二进制，他们当前位为1时想加一定是3，所以当前位余3等于0则说明单独那个数字在当前位是0，如果余3等于1，则说明单独的数字当前位是1。
建立32个空间的数组，记录每一位的情况最后余1还是0，每一位都要遍历原有值数组查看当前位1的个数，有1则res[i]++，最后对该位进行取余和赋值处理，用一个数m记录当前位数

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

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月7日下午4:15

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = [0] * 32
        m = 1
        sum = 0
        for i in range(32):
            for j in range(len(nums)):
                if (nums[j] & m) != 0:
                    res[i] += 1
            res[i] %= 3
            sum += res[i] * m
            m <<= 1
        return sum

相与后通过不等于零判断

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月7日下午4:12

//思路：依次的到32位二进制的每一位，乘上位权做累加
//时间O(n) 空间O(1)
public int singleNumber(int[] nums) {
        int result = 0;

        int bit = 1;    //代表当前位，以及位权

        for(int i = 0;i < 32;i++){//遍历每一个二进制位
            int yes = 0;    //记录所有数中，当前位是1的个数

            for(int j = 0;j < nums.length;j++){
                if((nums[j] & bit) == bit){
                    //当前位是1
                    yes++;
                }
            }

            yes = yes % 3;  //看看“一次数字”当前位是1还是0
            result = (yes == 1) ? result + bit : result;

            bit = bit << 1; //看下一位
        }

        return result;
    }

0 赞同 0 条回复

小吕普通 2023年7月7日下午3:36

c++实现
int singleNumber(vector& nums) {
vector binary(32,0);
for(int i = 0;i<nums.size();i++)
{
for(int j = 0;j<32;j++)
{
binary[j]+=(nums[i]&1);
nums[i]>>=1;
}
}
int ans = 0,t=3;
for(int i = 31;i>=0;i–)
{
ans<<=1;
ans |=binary[i]%t;
}
return ans;
}

0 赞同 0 条回复

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

共以下 24 个回答

MY

# 回答此问题取消回复

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

共以下 24 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复