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

lQl 永久会员 2024年12月16日下午7:54

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

class Solution {
    public int trainingPlan(int[] actions) {
        int one = 0;
        int two = 0;
        for (int ac : actions) {
            one = one ^ ac & ~two;
            two = two ^ ac & ~one;
        }

        return one;
    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月12日下午10:26

解题思路
– 数组中每个元素的二进制数，按倒数第1位，第2位…的顺序按位相加，相加结果%3=1，说明单独出现的数字第i位也是1
【题解1】

class Solution {
    public int trainingPlan(int[] actions) {
        // 元素1的二进制数：1001
        // 元素2的二进制数：1001
        // 元素3的二进制数：1001
        // 独立元素A的二进制数：1110
        // 倒数第1位：（1+1+1+0）/3=0，就是A的倒数第1位
        // 倒数第2位：（0+0+0+1）/3=1，就是A的倒数第2位
        // 倒数第3位：（0+0+0+1）/3=1，就是A的倒数第3位
        // 倒数第4位：（1+1+1+1）/3=1，就是A的倒数第4位

        // 倒数第i位，int总共只有32位
        int result = 0;
        int key = 1;
        for (int i = 0; i < 32; i++) {
            // 遍历每个元素
            int sum = 0;
            for (int j = 0; j < actions.length; j++) {
                // 【错误点】 actions[j] ^ 10 时，结果不是0和1，就为10
                // 两种正确的表达 (actions[j] & key) != 0 或者 (actions[j] & key) == key
                if ((actions[j] & key) != 0) {
                    sum = sum + 1;
                }
            }
            // 【错误点】 %3是取余数， /3是取除数
            result = result + key * (sum % 3);
            key = key << 1;
        }
        return result;

    }
}

错误点1：actions[j] ^ 10 时，结果不是0和1，而是10
错误点2： %3是取余数， /3是取除数

0 赞同 0 条回复

秋山丽奈普通 2024年12月10日下午9:26

思路：膜拜了状态机写法过于复杂。遂练习Map 代码

class Solution {

    public int trainingPlan(int[] nums) {
        Map<Integer, Integer> map = new HashMap();

        for(int i = nums.length - 1; i >= 0; --i){
            int key = nums[i];
            if(!map.containsKey(key)){
                // 如果之前没有遇到这一数字，则放入 map 中
                map.put(key, 1);
            }else{
                // 如果之前遇到过这一数字，则出现次数加 1
                map.put(key, map.get(key) + 1);
            }
        }

        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }

        return -1;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月10日下午9:06

class Solution {
    //思路：通过对actions数组中每一个数的最后一位依次进行求和操作，对3取余，即可获取出现一次数字
    //对应位的值。接着在每次循环中对该位进行十进制转换并加入res中
    public int trainingPlan(int[] actions) {
        int tmpRes,tmpNum;
        int x=1;
        int res=0;
        for(int i=0;i<32;i++){
            tmpRes=0;
            for(int j=0;j<actions.length;j++){
                tmpRes=tmpRes+(1&actions[j]);
                actions[j]=actions[j]>>1;
            }
            tmpNum=tmpRes%3;
            res=res+tmpNum*x;
            x*=2;
        }
        return res;
    }
}
时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

Kisara 普通 2024年12月10日下午8:04

方法一，看不懂位运算

class Solution {
    public int trainingPlan(int[] actions) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int n:actions){
            int data=map.getOrDefault(n, 0);
            if(data==0) map.put(n,1);
            else map.put(n,data+1);
        }

        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==1)
            return entry.getKey();
        }

        return 0;
    }
}

On On

位运算

public int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int c : nums) {
        // 尝试不同的表达式组合
        int tempa = (~a & b & c) | (a & ~b & ~c);
        b = (~a & ~b & c) | (~a & b & ~c);
        a = tempa;
    }
    return b;
}

On O1

0 赞同 0 条回复

Aatorx 永久会员 2024年12月10日下午3:30

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int ones = 0;
        int twos = 0;
        for (int actions : actions) {
            ones = ones ^ actions & ~twos;
            twos = twos ^ actions & ~ones;
        }
        return ones;
    }
};

统计各个元素二进制位的出现次数，对3取余数，若为0则说明出现了3次，若为1则说明出现了1次。因为有三种状态，所以分别用00，01，10来表示。定义第一位为one，第二位为two。对于第一位，可以发现变化规律为0->1->0->0;第二位变化规律为0->0->1->0;只有循序不同，规律相同，因此可以用同一个公式表达。遍历数组计算one跟two的数值。因为数组中只有出现三次跟一次两种状态，所以只有00，01两种，two恒为0，最后one即为结果。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

月下足迹普通 2024年12月10日上午11:11

// 用来统计每个位上1的出现次数
int[] bitCounts = new int[32];

    // 遍历数组中的每个数字
    for (int num : actions) {
        for (int i = 0; i < 32; i++) {
            // 统计 num 的第 i 位是否为 1
            bitCounts[i] += (num >> i) & 1;
        }
    }

    // 通过模 3 恢复教练的编号
    int result = 0;
    for (int i = 0; i < 32; i++) {
        if (bitCounts[i] % 3 != 0) {
            result |= (1 << i); // 将第 i 位加入到结果中
        }
    }

    return result;

0 赞同 0 条回复

jaron 普通 2024年12月10日上午10:23

class Solution {
    public int trainingPlan(int[] actions) {
        int m = 1, ans = 0;
        int[] res = new int[32];
        for (int i = 0; i < 32; i++) {
            // 统计每一位
            for (int action : actions) {
                if ((action & m) != 0) {
                    res[i] += 1;
                }
            }
            // 取余3消除出现三次的数
            res[i] = res[i] % 3;
            ans += res[i] * m;
            m = m << 1;
        }
        return ans;
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月10日上午10:05

class Solution {
public int trainingPlan(int[] actions) {
int[] k = new int[32];
for(int i = 0; i < actions.length; i++){
for(int j = 0; j < 32; j++){
k[j] += (actions[i] >> j & 1) 1 ? 1 : 0;
}
}
int res = 0;
for(int i = 31; i >= 0; i–){
res = res << 1;
if(k[i] % 3 1){
res = (res | 1);
}
}
return res;
}
}
思路：统计每一位出现的次数，超过三次的最后记录下来就是答案
时间：O（n）
空间：O（1）

0 赞同 0 条回复

迢迢星野普通 2024年12月9日下午11:08

class Solution {
    /**
     * 教学过程中，教练示范一次，学员跟做三次。该过程被混乱剪辑后，记录于数组 actions，其中 actions[i] 表示做出该动作的人员编号。请返回教练的编号。
     * 
     * 题意解读：获取只出现过一次的数，其他的数都出现三次
     * 
     * 解法一：哈希
     * 解法二：位运算
     *      出现过三次的数，对应的二进制位 1 出现的个数是 3 的倍数。统计所有元素二进制位 1 的个数，再对 3 取余，剩下的二进制数组成的数字就是结果。
     *   方法一：有限状态自动机
     *      所有数字中的某二进制位 1 的个数，存在 3 种状态，即：0、1、2
     *          若输入二进制位 0，则状态位不变
     *          若输入二进制位 1，则按照以下顺序转换：0 -> 1 -> 2 -> 0；可以使用二进制位表示这三种状态：00 -> 01 -> 10 -> 00，因此
     *      设置 one、two 分别表示两位二进制位。two one(00、01、10)
     *      状态如何转换？
     *          对于任意二进制位 x，有：
     *              异或运算： x ^ 0 = x; x ^ 1 = ~x
     *              与运算：   x & 0 = 0; x & 1 = x
     *          输入二进制位为 n，计算 one：
     *              if two == 0:
     *                  if n == 0:
     *                      one = one;
     *                  if n == 1:
     *                      one = ~one;
     *             if two == 1:
     *                  if n == 1:
     *                      one = 0
     *          可以转换为：
     *              if two == 0:
     *                  one = one ^ n;
     *              if two == 1:
     *                  one = 0;
     *          还可以转换为： one = one ^ n & ~two  
     *          计算 tow：two = two ^ n & ~one
     *    遍历完所有数字后，各二进制位都处于状态 00 和状态 01（取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 twos 恒为 0 ），因此返回 ones 即可。
     *  
     *  解法二：统计各个二进制位 1 的个数，对 3 取余，剩下的二进制位组成的数字就是结果
     * @param actions
     * @return
     */
    public int trainingPlan1(int[] actions) {
        int one = 0, two = 0;
        for (int action : actions) {
            one = one ^ action & ~two;
            two = two ^ action & ~one;
        }
        return one;
    }

    public int trainingPlan(int[] actions) {
        // int 类型
        int[] counts = new int[32];
        for (int action : actions) {
            // 统计每个二进制位上 1 的个数
            for (int i = 0; i < 32; i++) {
                // 更新第 i 位 1 的个数之和
                counts[i] += action & 1;
                // 第 i 位 --> 第 i + 1 位
                action >>= 1;
            }
        }

        // 将 counts 的每个二进制位对 3 取余，并组合成一个数字
        // 初始化结果变量为0，用于最终计算结果
        int res = 0;
        // 遍历counts数组，该数组的长度固定为32，表示二进制数字的每一位
        for (int i = 31; i >= 0; i--) {
            counts[i] %= 3;
            res <<= 1;
            res |= counts[i];
        }

        return res;
    }
}

思路：位运算 | 逐位相加，对 3 取余。
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

晓宇普通 2024年12月9日下午8:20

// 思路：逐位相加，分别对3取余。余数则为题解。
class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        if(actions.empty()) return -1;
        vector<int> bits(32, 0);
        int ans = 0;
        int m = 1;
        for(int i = 0;i < 32;i++){
            for(int j = 0; j < actions.size();j++){
                if((actions[j] & m) != 0)
                    bits[i] += 1;
            }
            bits[i] %= 3;
            ans += bits[i] * m;
            m = m << 1;

        }
        return ans;

    }
};
// o(n) o(1)

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复