剑指 Offer 56 - II. 数组中数字出现的次数 II(状态转移 位运算)

​​剑指 Offer 56 - II. 数组中数字出现的次数 II​​

难度中等38

在一个数组 ​​nums​​ 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

示例 2：

输入：nums = [9,1,7,9,7,9,7] 输出：1

解题思路：

我们可以发现，最后的数字假如第i位是1（二进制表示），那么第i位肯定有3*x+1个1，那么我们就思考第i位能不能进行转台转移。最终转移到一个合法的状态。

转移到红色框内的状态才是我们想要的。注意，假如我们想根据真值表表示一个数，例如：A=0 B=1 C=0我们想表示出C用A，B，那么我们可以写为~(~A & B).

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