题目
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
思考题：
如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,1,1,2,2,2,3,4,4,4]
输出：3

解法1：数位统计

从高到低枚举每个数位，如果该位为1的次数%3==1，说明只出现一次的数字这一位也是1
时间复杂度O(nlogn)，空间复杂度O(1)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            int cnt = 0;
            for (auto x: nums) {
                if (x >> i & 1) {
                    cnt++;
                }
            }
            if (cnt % 3 == 1)
                ans = ans * 2 + 1;
            else ans *= 2;
        }
        return ans;
    }
};

解法二：位运算

构建循环周期为3的二元自动机
时间复杂度O(n)，空间复杂度O(1)

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