一、 题目

给一个数组，其中只有一个数出现一次，其他的数都出现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
  
   >i)&1;
            }
            ans|=(bitint[i]%3)<