剑指offer 62- 数组中唯一只出现一次的数字

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 O(n)的时间和额外 O(1) 的空间，该怎么做呢？

样例

输入：[1,1,1,2,2,2,3,4,4,4]

输出：3

分析：有限状态自动机
贴出某大神的最优代码

来源leetcode
来源leetcode

返回值：

以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。

遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 twos 恒为 0 ），因此返回 ones 即可。

参考：leetcode

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;
    }
};

算法二：
统计每位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;*/
        int res = 0;
        for(int i=31; i>=0; --i) {
            //看每一位1的数量
            int cnt=0;
            for(auto x:nums)
                if(x>>i & 1) cnt++;
            res = res*2 + (cnt%3 == 1 ? 1 : 0);
            // if(cnt%3 == 1) res = res*2 + 1;
            // else res = res*2;
        }
        return res;
    }
};