跟着姚桑学算法-数组中唯一只出现一次的数字

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

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

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

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

思考题：

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

数据范围
数组长度 [1,1500]。

样例

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

输出：3

【题解】--- 状态转移

本题与上一题思路类似，上一题中，其他数都出现了两次，因此需要的状态转移方式是，如果出现两个1就抵消为0，用一个变量和异或运算即可实现，而本题是需要1出现三次时才会抵消，因此有三种状态，即1出现的次数为3k, 3k + 1, 3k + 2次

逐个位来看，要设计一个两位的状态转移，出现三个1时，循环抵消，出现0时不变，一个变量只能记录两种状态，因此要用两个变量来记录状态，用one和two两个变量来记录1出现次数
00表示1出现3k次，01表示1出现3k + 1次，10表示1出现3k + 2次

真值表

two     one     x       two     one
0       0       1       0       1   
0       1       1       1       0
1       0       1       0       0
0       0       0       0       0
0       1       0       0       1
1       0       0       1       0

先看one的状态转移方程

 one = (~one & ~two & x) | (one & ~two & ~x)
     = ~two & ((~one & x) | (one & ~x))
     = ~two & (one ^ x)

同理，再用转移后的one来求two的状态转移方程；

这里，one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2；
因此如果题目改为，有一个数出现了两次，则返回two即可.

复杂度分析：

时间复杂度O(n)。

C++代码实现：

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