只出现一次的数

136. 只出现一次的数字

/*
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4
*/class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0;i<nums.size();i++){
            ans^=nums[i];
        }
        return ans;
    }
};

面试题56 - II. 数组中数字出现的次数 II

/*
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bit[32]={0};
        int n = nums.size();
        for(int i =0;i<n;i++){
            long long  temp = 1;
            int num = nums[i];
            for(int j = 31;j>=0;j--){
                if((temp & num)!=0){
                    bit[j]++;
                }
                temp<<=1;
            }
        }
        // for(int i=0;i<32;i++){
        //     cout<<bit[i]<<" ";
        // }
        // cout<<endl;
        int ret = 0;
        long long temp = 1;
        for(int i = 31;i>=0;i--){
            if(bit[i]%3==1){
                ret^=temp;
            }
            temp<<=1;
        }
        return ret;
    }
};

260. 只出现一次的数字 III

/*
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
输入: [1,2,1,3,2,5]
输出: [3,5]
*/
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ret;
        int ans = 0;
        for(int i = 0;i<nums.size();i++){
            ans^=nums[i];
        }
        int x = 0;
        while((1<<x & ans) ==0){
            x++;
        }
        cout<<x<<endl;

        int ret1 = 0;
        int ret2 = 0;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] & (1<<x)){
                ret1^=nums[i];
            }
            else{
                ret2^=nums[i];
            }
        }
        ret.push_back(ret1);
        ret.push_back(ret2);

        return ret;
    }
};