数组中数字出现的次数(位运算的运用)

57 阅读 0 评论 38 点赞

我是靠谱客的博主满意钢笔，最近开发中收集的这篇文章主要介绍数组中数字出现的次数(位运算的运用)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背景知识：
若x是任意整数，则有：

x^x=0;
x^0=x;

三道题：

一个数组，其中只有一个数只出现一次，其他数字均出现两次，求只出现一次的数
答：将所有数异或一遍，最终结果即所求
一个数组，其中有两个数只出现一次，其他数字均出现两次，求只出现一次的数
答：记只出现一次的数分别为a, b;
所有数字异或和的值为a^b!=0;
记a^b的二进制表示在inx位上为1；
数组中在inx位上为1的数字的异或和为a，数组在inx位上为0的数字的异或和为b；
一个数组，其中只有1个数只出现一次，其他数均出现三次；
cnt[i]记录二进制表示在i位上为1的数字的出现次数；
出现一次的数字的每一位上1出现的次数均模3等于1；
然后将模三等于1的位置为1就是答案

问题一
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans=0;
        for(int i=0; i<nums.size(); i++)
            ans^=nums[i];
        return ans;
    }
};

问题二
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int sum=0;
        for(int i=0; i<nums.size(); i++)
            sum^=nums[i];
        int inx=0;
        while(1){
            if(sum&1) break;
            sum>>=1;
            inx++;
        }
        vector<int> vec;
        vec.push_back(0);
        vec.push_back(0);
        int cnt, t;
        for(int i=0; i<nums.size(); i++){
            t=nums[i];
            cnt=0;
            while(cnt<inx && t){
                cnt++;
                t>>=1;
            }
            if(t&1) vec[0]^=nums[i];
            else vec[1]^=nums[i];
        }
        return vec;
    }
};

问题三
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans=0;
        int cnt[35];
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<nums.size(); i++){
            int inx=0;
            int x=nums[i];
            while(x){
                if(x&1) cnt[inx]++;
                x>>=1;
                inx++;
            }
        }
        for(int i=0; i<=32; i++){
            if(cnt[i]%3)
                ans+=(1<<i);
        }
        return ans;
    }
};