一.剑指 Offer II 004. 只出现一次的数字

1.题干及思路

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,100]
输出：100

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/

要点：位运算

思路：用一个32位vector，每个数对应二进制位在该vector中加1，最后遍历一遍vector如果%3==1则说明是那剩余一个数的位数之一

2.C++实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> tmp(32,0);
        int answer = 0;
        for(auto x:nums){
            for(int i=0;i<32;i++){
                if((x&1)==1) tmp[i]++;
                x>>=1;
            }
        }

        int mul = 1;
        for(int i=0;i<32;i++){
            if(tmp[i]%3==1){
                answer+=mul;
            }
            if(i<31) mul<<=1;
        }
        return answer;
    }
};