题目描述

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

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

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

样例

输入：[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即可

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