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

=.= 普通 2024年4月5日下午7:29

class Solution {
public int trainingPlan(int[] actions) {
int[] res = new int[32];
int m = 1;
int ans = 0;

    for(int i=0; i<32; i++){
        for(int j=0; j<actions.length; j++){
            if((actions[j] & m) != 0){
                res[i]++;
            }
        }

        res[i] = res[i] % 3;
        ans += res[i] * m;
        m = m << 1;
    }

    return ans;
}

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

0 赞同 0 条回复

NULL 普通 2024年3月26日下午3:12

public int trainingPlan(int[] nums) {
// 创建一个长度为 32 的数组 res，用于统计每个二进制位上出现的次数
int[] res = new int[32];
// 初始权值 m 为 1
int m = 1;
// 初始化结果 sum 为 0
int sum = 0;

    // 遍历每个二进制位
    for (int i = 0; i < 32; i++) {
        // 统计数组中所有数字在当前二进制位上出现的次数
        for (int j = 0; j < nums.length; j++) {
            // 如果当前数字 nums[j] 在当前二进制位上为 1，则 res[i] 加 1
            if ((nums[j] & m) != 0) {
                res[i]++;
            }
        }

        // 对统计结果取模，得到只出现一次的数字在当前二进制位上的值
        res[i] = res[i] % 3;
        // 将当前二进制位上的值加入到最终结果 sum 中
        sum = sum + res[i] * m;
        // 更新权值 m，用于处理下一个二进制位
        m = m << 1;
    }

    // 返回最终结果
    return sum;
}

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月23日下午7:33

class Solution {
    public int trainingPlan(int[] actions) {
        int[] res = new int [32];
        int m=1;
        int sum=0;

        for(int i=0;i<32;i++){
            for(int j=0;j<actions.length;j++){
                if((actions[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 条回复

南梁陈庆之普通 2024年3月23日下午5:59

位运算有点难，还是用hashmap，后面有空再看

class Solution {
    public int trainingPlan(int[] actions) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < actions.length;i++) {
            int key = actions[i];
            if (map.containsKey(key)) {
                map.put(key, map.get(key) + 1) ;
            } else {
                map.put(key, 1);
            }

        }

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

0 赞同 0 条回复

mpweixin用户普通 2024年3月21日下午11:09

public int[] sockCollocation(int[] sockets) {
int x=0,y=0;
int n=0;
int m=1;
for(int num:sockets){
n^=num;
}
while((n&m)0)
m<<=1;
for(int num:sockets){
if((num&m)!=0) x^=num;
else y^=num;
}
return new int[] {x,y};

思路：求单个不重复出现的值时一次异或即可
求两个的时候根据2者异或的值来确定哪一位是不一样的再将整组数据分成两个集合根据这个位来分在两个集合中分别异或即可得到这两个值

0 赞同 0 条回复

神经蛙普通 2024年3月21日上午12:12

class Solution {
public:
int trainingPlan(vector& actions) {
int bit[32] = {0};
int m = 0;

    for(int num : actions)
    {
        for(int i = 0; i< 32 ; i++)
        {
            if(num & 1) bit[i]++;
            num >>= 1;
        }
    }

    for(int j =31; j>=0; j--)
    {
        m <<= 1;
        m |= bit[j] % 3 ;

    }
    return m;
}

};
时间复杂度O(n)，空间复杂度为O(1)

0 赞同 0 条回复

kfaebot 普通 2024年3月20日下午10:23

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int answer=0;
        for(int i=0;i<32;i++){
            //对于int的每一位
            int bit=0;
            //计算每一位上所有数在这一位上的和
            for(int j=0;j<actions.size();j++){
                if(((actions[j]>>i)&1)!=0){
                    bit+=((actions[j]>>i)&1);
                }
            }
            //对3取余
            answer+=((bit%3)<<i);
        }
        return answer;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月20日下午9:40

java
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.put(key, 1);
        }else{
            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 条回复

言之命至普通 2024年3月20日下午9:32

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32]; //整型为32个bit
        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]++;//用来统计二进制的第m位是否为1，为1则++
                }
            }

            res[i] = res[i] % 3;//对3取余能够过滤出单身号所在i位置的二进制位
            sum = sum + res[i] * m;//统计化成十进制表示
            m = m << 1;//左移1位用于统计下次的二进制位
        }

        return sum;
    }
}

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

0 赞同 0 条回复

Jimmy 普通 2024年3月20日下午8:09

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

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int sum = 0;
        vector<int> res(32,0);//整形为32个bit
        int m = 1;
        for(int i=0;i<32;i++){
            for(int j=0;j<actions.size();j++){
                if((actions[j]&m) != 0){
                    res[i]++;//用来统计二进制的第m位是否为1，为1则++
                }
            }
            res[i] = res[i]%3;//对3取余能够过滤出单身号所在i位置的二进制位
            sum += res[i]*m;//统计化成十进制表示
            m = m << 1;//左移1位用于统计下次的二进制位
        }
        return sum;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月20日下午4:17

//方法一时间On 空间O1
class Solution {
public int trainingPlan(int[] actions) {
int ans = 0;
int p = 1;
for(int i = 0 ; i < 32; i++){
int sum = 0;
for(int j = 0; j < actions.length; j++){
sum += (actions[j] & p)!=0 ? 1 : 0 ;
}
ans += p * (sum % 3);
p <<= 1;
}
return ans;
}
}
//方法二有限状态机//时间On 空间O1
class Solution {
public int trainingPlan(int[] actions) {
int A = 0;
int B = 0;
for(int action :actions){
int temp = A;
A = A & (~B) & (~action) | (~A) & B & action;
B = ~temp & (B ^ action);
}
return B;
}
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月20日上午8:30

打卡

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int m = 1;
        int res = 0;
        for(int i = 0; i < 32; ++i) {
            int sum = 0;
            for(int j = 0; j < actions.size(); ++j) {
                if((actions[j] & m) != 0) sum++;
            }
            sum = sum % 3;
            res += sum * m;
            m = m << 1;
        }
        return res;
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月20日上午8:30

打卡

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int m = 1;
        int res = 0;
        for(int i = 0; i < 32; ++i) {
            int sum = 0;
            for(int j = 0; j < actions.size(); ++j) {
                if((actions[j] & m) != 0) sum++;
            }
            sum = sum % 3;
            res += sum * m;
            m = m << 1;
        }
        return res;
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月20日上午8:30

打卡

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        int m = 1;
        int res = 0;
        for(int i = 0; i < 32; ++i) {
            int sum = 0;
            for(int j = 0; j < actions.size(); ++j) {
                if((actions[j] & m) != 0) sum++;
            }
            sum = sum % 3;
            res += sum * m;
            m = m << 1;
        }
        return res;
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月20日上午6:18

class Solution:
def singleNumber(self, nums: List[int]) -> int:
return (3*sum(list(set(nums)))-sum(nums))//2
o 1 时间

0 赞同 0 条回复

MARS 普通 2024年3月20日上午12:17

/**
 * @param {number[]} actions
 * @return {number}
 */
var trainingPlan = function (actions) {
    let res = new Array(32).fill(0)
    let m = 1
    let sum = 0
    for (let i = 0; i < 32; i++) {
        for (let j = 0; j < actions.length; j++) {
            if ((actions[j] & m) != 0) {
                res[i]++
            }
        }
        res[i] = res[i] % 3
        sum = sum + res[i] * m
        m = m << 1  //进位
    }
    return sum
};

0 赞同 0 条回复

紫芝普通 2024年3月19日下午11:47

位运算：

“`c++
class Solution {
public:
int trainingPlan(vector& actions) {
int nums[32] = {0};
for (int act: actions) {
for (int i=0; i<32 && act != 0; i++) {
nums[i] += act & 1;
act >>= 1;
}
}
int ans = 0;
for (int i=31; i>=0; i–) {
ans <<= 1; ans |= nums[i] % 3; } return ans; } }; ```

0 赞同 0 条回复

王位詮釋普通 2024年3月19日下午9:58

用哈希表写的：
class Solution {
    public int trainingPlan(int[] actions) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<actions.length;i++){
            if(map.containsKey(actions[i])){
                int temp = map.get(actions[i]);
                map.put(actions[i],temp+1);
                continue;
            }
            map.put(actions[i],1);
        }
        int result = 0;
        for(Integer integer:map.keySet()){
            if(map.get(integer)==1){
                result = integer;
                break;
            }
        }
        return result;
    }
}
用位运算写的
class Solution {
    public int trainingPlan(int[] actions) {
        int[] res = new int[32];
        int sum = 0;
        int m = 1;
        for(int i = 0;i<32;i++){
            for(int j=0;j<actions.length;j++){
                if((actions[j]&m)!=0){
                    res[i]++;
                }
            }
            res[i] = res[i]%3;
            sum = sum+res[i]*m;
            m = m<<1;
        }
        return sum;
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月19日下午9:30

class Solution {
public:
    int trainingPlan(vector<int>& actions) {
        vector<int> res(32, 0);
        unsigned int m = 1;
        int sum = 0;
        for(int i = 0; i < 32; ++i){
            for(int j = 0; j < actions.size(); ++j){
                if((actions[j] & m) != 0){
                    res[i] ++;
                }
            }
            // 计算sum所对应的的位置是0还是1
            res[i] %= 3;
            // res[i]==0的时候，sum不变
            // res[i]==1的时候，sum加上m
            sum = sum + res[i] * m;
            m = m << 1;
        }

        return sum;
    }
};

0 赞同 0 条回复

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

共以下 19 个回答

# 回答此问题取消回复

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

共以下 19 个回答

# 回答此问题 取消回复

# 回答此问题取消回复