剑指offer刷题 数组中只出现一次的两个数字

数组中只出现一次的两个数字

题意
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例
输入：[1,2,3,3,4,4]
输出：[1,2]
思路 一看到这种数组中只出现几次的数字就要想到用位运算的性质进行解答
解题步骤
1、先找到x和y异或的和
2.找异或和的第k位是1，根据第k位是1还是0将集合进行分开最后得到的一个集合是x另一个结合是y;

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        vector<int> res;
        if(nums.empty()) return res;
        int sum=0;
        for(auto x:nums) sum^=x;
        int y=0;
        int k=0;
        while(!(sum>>k&1)) k++;
        for(auto x:nums)
        {
            if(x>>k&1)
            y^=x;
        }
        /*res.push_back(y);
        res.push_back(sum^y);
        return res;*/ 
        return vector<int> {y,sum^y}; //数组返回的小技巧
    }
};

数组中唯一只出现一次的数字

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。

样例

输入：[1,1,1,2,2,2,3,4,4,4]
输出：3
这道题目可以用状态机做到时间复杂度为o(n)和额外的空间为o(1)
第一种思路 遍历统计数组中的每个数字，统计每一位出现1的次数，然后每一位mod3等于0说明这个数出现了三次，所以最后的结果就是出现了1次的数字。
时间复杂度o(32n) 空间复杂度o(32)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int n=nums.size();
        int bit[32]={0};
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<32;j++)
            {
                if((nums[i]>>j)&1)
                {
                    bit[j]++;
                }
            }
        }
        int res=0;
        for(int i=0;i<32;i++)
        {
            if(bit[i]%3)
            {
                res+=1<<i;
            }
        }
        return res;
        
    }
};

用状态机做到时间复杂度为o(n)和额外的空间为o(1)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (auto x : nums)
        {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }
};