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

Sheng 永久会员 2023年9月13日下午6:27

看的答案做的

    //数组中数字出现的次数2
    public int singleNumber(int[] nums) {
        int result = 0;

        int binary = 1;
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res = 0;
            for(int j = 0; j < nums.length; j++) {
                if(nums[j] & binary != 0) {
                    res++;
                }
            }
            result += res % 3 * binary;
            binary = binary << 1;
        }
        return result;
    }

0 赞同 0 条回复

sc_Yang 普通 2023年9月7日上午8:47

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x=0,y=0,n=0,m=1; // m是用来与出不同的二进制位置的
        // 异或第一遍得到结果想x^y
        for(int num : nums){
            n = num^n;
        }
        // 找到二进制x和二进制y任意一个不同的位
        while((n&m) == 0){
            m = m<<1;
        }
        for(int num : nums){
            if(num & m){ // 该位置为1的所有数
                x = x^num;
            }else{ // 该位置为0的所有数
                y = y^num;
            }
        }
        return vector<int>{x, y};
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月6日上午11:50

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        for (int n : nums) {
            int i = 0;
            while (n > 0) {
                if (n % 2 == 1) {
                    count[i] ++;
                }
                i ++;
                n >>= 1;
            }
        }
        //也可以解决一个数字出现一次，其它出现m次
        //有限状态机的化，其实就是三个1会转换到原来的状态，0不会转变状态，并且m次的化，就需要有m个状态
        //也可以直接使用哈希，时间复杂度应该差不多，空间复杂度哈希表是O(N)，N为不重复元素的个数，位统计的空间复杂度为O(32)
        int res = 0, m = 3;
        for (int i = 0; i < count.length; i ++) {
            if (count[i] % m == 1) {
                res += Math.pow(2, i);
            }
        }
        return res;
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月5日下午3:48

思路：维护一个长度32的数组，对应整形的32位二进制位置，统计每个位的1出现次数，每个位%3得到的就是只出现一次的，得到的数组转化为10进制即可
复杂度：时间复杂度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 num : nums) {
                if ((num & m) != 0) {
                    res[i]++;// 当前位为1,计数加1
                }
            }
            res[i] = res[i] % 3;// 过滤出现3次的
            sum += res[i] * m;
            m <<= 1;
        }
        return sum;
    }
}

0 赞同 0 条回复

c 普通 2023年9月1日上午11:14

统计1

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月31日上午9:38

// 位运算 时间复杂度O(n)<空间复杂度O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i=0,sub=0;i<32;++i,sub=0)
        {
           for(auto num:nums) sub+=(num>>i)&1;
           if(sub%3) res|=(1<<i);
        }
        return res;
    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月31日上午12:18

笨方法，哈希表

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num, (int)map.get(num)+1);
            }else{
                map.put(num, 1);
            }
        }

        for(int num : nums){
            if(map.get(num) == 1){
                return num;
            }
        }
        return 0;
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月30日下午11:57

地哥解法

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

JustRtn 普通 2023年8月30日下午4:28

不看题解不会做系列（非暴力法）
看到有个大神题解很好，有数电基础很容易理解，记录一下

class Solution {
    public int singleNumber(int[] nums) {
        // 可以设计一种逻辑，使数字出现 3 次时，该逻辑的结果为 0（即只有 0，1，2 三种状态）
        // 其实就是一个 三进制
        // 一位二进制数只能存储 0 和 1 两种状态，所以我们需要用到两位二进制
        // 设两位二进制数的高位为 A，低位为 B。C 是输入变量
        // 表示的三种情况为 ： 0次：00(A=0,B=0), 1次：01(A=0,B=1), 2次：10(A=1,B=0) 
        // 注：11(A=1,B=1) 为无效输入

        // 画出关于 A 的卡诺图（AB为11的结果是不重要的，用 x 表示）：
        //  AB\C |  0  |  1
        //  =================
        //    00 |  0  |  0
        //    01 |  0  |  1        ====> 得到 A = BC + AC'
        //    11 |  x  |  x
        //    10 |  1  |  0

        //  画出关于 B 的卡诺图
        //  AB\C |  0  |  1
        //  =================
        //    00 |  0  |  1
        //    01 |  1  |  0        ====> 得到 B = BC' + A'B'C
        //    11 |  x  |  x
        //    10 |  0  |  0

        // 很明显啊，我们需要的就是只出现一次的情况 01（A=0，B=1），即 B 的结果
        int A = 0, B = 0;
        for (int C : nums) {
            int tmp = A;
            A = (B & C) | (A & ~C);
            B = (B & ~C) | (~tmp & ~B & C);
        }
        return B;
    }
}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复