学步园

题目的描述是这样的：Given an array of integers, every element appears three times
except for one. Find that single one.Note:Your
algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

要求复杂度为O(n),而且不能用额外的内存空间。

这个比之前那个Single Number I 难多了。。在网上搜的答案都看了半天才看懂。。

因为十进制的数字在计算机中是以二进制的形式存储的，所以数组中的任何一个数字都可以转化为类似101001101这样的形式，int类型占内存4个字节，也就是32位。那么，如果一个数字在数组中出现了三次，比如18，二进制是10010，所以第一位和第四位上的1，也都各出现了3次。

因此可以用ones代表只出现一次的数位，twos代表出现了两次的数位，xthrees代表出现了三次的数位。

 public int singleNumber(int[] A) {
        int ones=0;
        int twos=0;
        int xthrees=0;
        for(int i = 0;i <A.length;i++){
                twos ^= (ones&A[i]);
                ones ^= A[i];
                xthrees = ~(ones&twos);
                twos &= xthrees;
                ones &=xthrees;
         }
         return ones;
    }

遍历结束后，ones即为所求。