问题 1： 

给定一个数组，除了一个数出现1次之外，其余数都出现2次。找出出现一次的数。

如：{1, 2, 1, 2, 7}, 找出7

要求 时间复杂度为线性，并且不能有额外的空间辅助

 

/*thinking : 首先按照常规思想从数组中找数字，可以利用现有的数据结构map来装,然后找，但是细想一下，就知道，map的开销是比较大的，在装之前得先查找一遍不说，而且还会浪费空间

* 所以pass， 其次想到利用数组下标，来记录出现的数字个数，然后找，时间复杂度中：找出最大值可以为n，然后再遍历一遍找到数组中为1的下标，时间复杂度线性符合，但是，but，otherwise，首先不满组条件

* 有了额外的空间辅助不说，万一这个出现一次的数字很大，那岂不是浪费很多空间开销，不划算，pass

* 所以，其实以我浅薄的认知，看到条件中是时间复杂度为线性，而且不能有空间开销的时候，这样非常苛刻的要求，基本就要往基本的二进制和逻辑上靠边了

* 再来一个所以，从二进制上想，出现两次的数字的在二进制上某一位置上1的个数在相加之后肯定能整除2，只有一个的那个数单看肯定不能了，因为这个数不管哪一位要不是0要不是1，是不可能整除2的，有了这个想法之后

* 现在设计算法来实现一种逻辑可以让二进制上某一位出现0， 1，若是再来一个1，满2（某个数字出现两次）的时候，不能进位，直接请0，所以直接的算术加法是不可能了，欸，巧了一点就是，异或 这个东东 满足这个要死不死的逻辑，异或就是两个相同清0，

* 两个不同保留，也就是和自己异或清0，与别人异或保留。正好满足

* */

老规矩 ， 贴上代码：

public static void findOneFromTwo(int[] a){        int ans = a[0];        for(int i = 1; i < a.length; ++i){            ans ^= a[i];        }        System.out.println(ans);    }

 

写到这里不得感叹一下逻辑的伟大，毕竟这玩意儿是老祖宗亿万年留下的产物，而且也是不分学科，不分等级，没有任何界限和门槛的东西，说的有点抽象和哲学了，hhhhhhhh，好，收，现在进入下一个问题:

问题 2： 

给定一个数组，除了一个数出现1次之外，其余数都出现3次。找出出现一次的数。

如：{1, 2, 1, 2, 1, 2, 7}, 找出7

要求 时间复杂度为线性，并且不能有额外的空间辅助

看到这里，是不是有道友会说，这跟上一题不是一样吗？ 嗯，有一样，但又不一样，你再仔细看看，多填了一组后，前面的异或逻辑是不是满足我们的需求了呢？这里我再重点回顾一下上面的需求：现在设计算法来实现一种逻辑可以让二进制上某一位出现0， 1，若是再来一个1，也就是满2（某个数字出现两次）的时候，不能进位，直接请0， 注意这里是满2的前提下我们想到了异或的逻辑，但是这里是出现三次，如果再用异或，那就是满2次的时候异或清0，再来一次，又出现了，所以不能单独只用异或了，但是一样的地方就是我们的需求还是差不多的，只不过这里便要变成三进制： 设计算法来实现一种逻辑可以让三进制上某一位出现0， 1，2，若是再来一个1，满3的时候，不能进位，直接请0，但是我们在设计的时候其实是基于二进制的，所以出现2，这个是不可能的情况，所以，我们就需要引进多一个变量，我这里用ones 代表二进制中某一位出现1次1的情况记录，（1 mod 3）后的结果， twos 代表二进制中某一位出现两次的情况记录 （2 mod 3）的结果，现在要实现一组逻辑满足出现三次就清0.

先贴上代码然后细讲一下里面逻辑部分：

public static void findOneFromTree(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);            ones &= xthrees;            twos &= xthrees;                    }        System.out.println(ones);    }

 

嗯，逻辑好的道友肯定看懂了，但是我还是要讲一下，因为我也是琢磨了许久才相通的这个逻辑：

twos |= (ones & a[i]);

这一句，先看后面一部分是取与操作，含义是对于数组中数字的数字和现在记录的ones 满足两个都是真的情况，也就是时候ones上会有满二的情况，也就是出现两次，但是不能进位，但也不能清0，因为要记录下来2的情况，所以只能在这个条件下，用twos 来记录，所以用的或操作记录下这个1，也就是twos 为真了，

ones ^= a[i];

， 异或就不用说了吧，就是记录下ones的为真的情况

xthrees = ~(ones & twos);

这句话的含义其实是遇到三清0操作的前提，当ones 和 twos 都满足的时候，就是说明两个都为真，也就是说满三了，需要请0， 所以就只能取反，或者在二进制上看作为算模的操作

后面两句就是实实在在开始的清0操作来更新ones 和 twos的记录，让他们都为0，毕竟我们的需求宗旨是满三后，就清0，所以ones所代表的一次需要变成0，twos代表的两次也需要清0，当然如果不是只有一次，也就是twos为false的时候，在二进制上也无妨，因为xthree是两者的与操作后取反，或者在二进制上可看作取模的操作。

嗯，反正我觉的是难理解的，置于能不能理解的更深层次就看各位道友的造化了，或者有其他见解的望留言告知。