原创 以另一种位图的思想来解决一道OJ题目

前言：

以前所接触到的位图的思想都是以1位的形式去存储某个数出现的次数是1次还是0次。常见的例子不外乎在《编程珠玑》上的开篇例子里，1千万个数的排序统计，用1.25M的内存空间就可以达到遍历一遍输入数据而排序好的目的。这种思想是通用的么？也就是说，假如输入数据不再是0次或者1次，而是2次或者更多的时候，如何再次用上这种思想呢？请看下面题目

题目：

输入一个数组，数组有int类型整数若干，若有其中一个是出现一次或者两次，其他数字都是出现3次，要求在时间复杂度在O(N)上限里求出那个数字。

解法一

生搬硬套位图的思想，既然最多出现3次，那么我用两个bit位来存储一个数出现的个数。那么假如输入是2千万个数的时候，所需要的空间是2.5M。20亿个数的时候，需要的是250M。显然，这种思想还是不太好，虽然符合题目要求。像这样处理海量数据肯定是要被毙掉的。可以尝试着做改进，改进思路是分批处理，如面对20亿的数据，我只自定义一个1千万数的空间，2.5M，然后每次只是处理1千万的数，如果没有出现目标数，那么再处理下一个一千万的数（按照大小区分范围）。应该也算得上一种尚可的思路。

解法二

基于位图思想的变形，我用32个数来存储所有的数中0~31位出现的个数，然后对3取余，如果是2，证明这个数的某一个位出现过2次，依次从0位推到31位。最后相或即可。

这种解法只用到了32 * 32 bit的空间，至于时间，因为需要对每个位进行统计，需要遍历输入数据32次， 32* N，可依然是符合题目的O(N)要求。 

这种解法，在时间上应该是要比解法一耗时少一些。第一种解法需要遍历数据约210次，因为int类型最大值是21亿（假如不包括负数），那么就是210个1千万数了。

空间也少很多。无疑是比较好的。

    public static int singleNumber(int[] A) {