学步园

一、     题目

给一个数组，其中只有一个数出现一次，其他的数都出现3次，请找出这个数。要求时间复杂度是O(n)，空间复杂度O(1)。

二、     分析

第一次遇见这样的题，真心没思路….前面的signal number中我们可以直接异或得到结果，很显然这个更复杂了。暴力解法或排序显然无法满足时空要求，所以还得回到位运算上，既然是同样的数出现了三次，我们可以想到他们的二进制表达对应的位置上相同。对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。如果我们在每一个位置上取到出现1的次数，并进行余3操作，则可消除该数。

例如:A[]={2,3,4,3,2,2,3}

     0010

     0011

     0100

     0011

     0010

     0010

     0011

=   -0-1-6-3-(1的个数)

     0100

int型数据为32位，可以开一个大小为32的int型数组存储N个元素的各个二进制位的1出现的次数，然后将该次数模3运算。

PS:后面几种方法刚开始真心没看懂….自己弱菜

class Solution {
public:
    int singleNumber(int A[], int n) {
        int bitint[32]={0};
        int ans=0;
        for(int i=0; i<32; i++){
            for(int j=0; j<n; j++){
                bitint[i]+=(A[j]>>i)&1;
            }
            ans|=(bitint[i]%3)<<i;
        }
        return ans;
    }
};



class Solution {
public:
    int singleNumber(int A[], int n) {
        int one,two,three;
        one=two=three=0;
        for(int i=0;i<n;i++)
        {//一定是出现3次，2次，1次这样的顺序，如果反过来的话，先更新了one的话，会影响到two和three的
            three =  two & A[i];//已经出现了两次，还出现了一次
            two = two | one & A[i];//出现了1次又出现了1次，在加上以前已经出现了2次的，为新的出现了2次的
            one = one | A[i];//出现了1次
            //将出现3次的其出现1次2次全部抹去
            one = one & ~three;
            two = two & ~three;
        }
         return one;
    }
};


int sol2(int A[], int n)
{
    int one = 0, two = 0, three = 0;
    for (int i = 0;i < n;++i) {
        two |= one & A[i];      新的那个数和出现过一次（one） & 就是出现过两次，加到Two里面
        one ^= A[i];               和one  ^  如果没出现过，什么都不会发生；如果出现过，自然消失。
        three = one & two;   如果出现第三次的必然是one 和 two的合并内容
        one &= ~three;         把第三次出现的从one删除
        two &= ~three;         把第三次出现的从two删除
    }
    return one;
}

class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0;
        
        for (int i = 0; i < n; i++) {
            one = (one ^ A[i]) & ~two;
            two = (two ^ A[i]) & ~one;
        }
        
        return one;
    }
};