一道能做出来就脚踢BAT的高难度算法题：在元素重复三次的数组中查找重复一次的元素

我们看一道难度很高的查找类算法题，如果你真能在一小时内给出正确的算法和编码，那么你随便在BAT开口年薪一百万都不算过分。我们先看题目：给定一个数组，它里面除了一个元素外，其他元素都重复了三次，要求在空间复杂度为O(1)，时间复杂度为O(n)的约束下，查找到只重复了一次的元素。

在一个小时内设计出满足条件的算法并编写正确的代码，难度相当大。我们先从简单的角度思考，一种做法是先将数组进行排序，然后从头到尾遍历一次，就可以找到重复一次的元素，但问题在于排序所需要时间为O(n*lg(n))，这就超出了题目对时间的限制，从题目的要求看，不能分配多余空间，并且时间复杂度只能是O(n)，这意味着算法必须对数组遍历1次就要找出给定元素。

普通的查找算法在给定条件约束下都无法适用，此时我们必须考虑复杂抽象的位操作。根据题目描述，除了一个元素外，其余元素都重复了三次，我们拿到一个重复3次的元素，将其转换为二进制，如果某个比特位的值是1，那么如果我们遍历一次数组，该位置见到的1一定超过3次以上。看一个具体例子，假设一个重复三次的元素值是2，它的二进制格式为011,那重复三次就是010，010，010,于是下标为0和1的比特位的1就出现了3次，假设我们有一种机制，能够在某个比特位上检测到该位出现的1有三次就清零，那么所有重复三次的元素将会被清除，只剩下重复1次的元素。

我们看个具体例子，例如2,2,2,3，他们对应的二进制位010,010,011,010，把他们累起来有： 010 010 010 =(下标为1的比特位上出现三次1，因此把该位清除为0)=>000 011 011 => 011 => 3 从上面例子看到，我们只要监控每一个比特位，一旦发现在该比特位上出现三次1就把它清0，由于除了一个元素外，其他元素都重复了三次，因此相应的比特位上肯定都相应出现三次1，而只重复1次的元素在相应比特位上的1只出现1次因此不会被清零，由此遍历一次后，只有出现1次的元素的比特位上的1保留下来，这样我们就把出现1次的元素给抽取出来。

问题在于我们如何实现监控每个比特位是否出现三次1的机制。我们设置两个变量towOnes,oneOnes，当某个比特位第一次出现1时，我们把oneOnes对应的位置比特位设置为1，当某个比特位第二次出现为1时，把oneOnes对应的比特位设置为0，在twoOnes对应的比特位设置为1，当对应比特位第三次出现1时，将towOnes对应比特位设置为0，下面的代码可以实现比特位的监控机制：

//E是当前从数组中读入的元素
int T = towOnes;
int O = oneOnes;
twoOnes = T ^ (T & E);  //如果某个比特位上出现三次1的话将其清除
E = E ^ (T & E);  //把出现三次1的比特位上的1清除
twoOnes = twoOnes | (E & O) ; //如果某个比特位上出现两次1，将其设置到twoOnes对应的比特位上
oneOnes = O ^ E ; //将出现1次的比特位设置到oneOnes上

我们用实例将上面步骤走一遍以便获得跟深刻理解，假设当前数组内容为：2，3，2，2，一开始towOnes =0, oneOnes = 0,一开始读入的元素为2，二进制位010，于是执行代码所示的四个步骤： towOnes = 0 ^ (0 & 010) = 0; E = 010 ^ (0 & 0) = 010 twoOnes = 0 | (0 & 0) = 0; oneOnes = 0 ^ 010 = 010 于是，T = 0, O = 010 我们看下标为1的比特位第一次出现1时，oneOnes对应的比特位也设置为1.我们再看输入第二个元素的处理，第二个元素是3，二进制位011，于是有： twoOnes = 0 ^ (0 & 011) = 0 E = 011 ^ (0 & 011) = 011 twoOnes = 0 | (011 & 010) = 010 oneOnes = 010 ^ 011 = 001 于是有T = 010, O = 001 从上面结果看出，下标为1的比特位连续出现两个1，于是twoOnes对应的比特位也设置为1,oneOnes对应比特位设置为0，下标为0的比特位第一次出现1，所以oneOnes对应比特位设置为1. 再次读入第三个元素2，其二进制位010，于是有： twoOnes = 010 ^ (010 & 010) = 0 E = 010 ^ (010 & 010) = 0 twoOnes = 0 | (0 & 001) = 0 oneOnes = 001 ^ 0 = 001 于是有T=0, O=001 从上面运算过程我们看到，再次读入010时，twoOnes在给定下标的位置也是1，也就是下标为1的比特位上此时看到1第三次出现，于是把twoOnes在相应位置上的比特位清0，oneOnes比特位上的数字保持不变。 读入最后一个元素是2，也是010，相应的运算过程有： twoOnes = 0 ^ (0 & 010) = 0 E = 010 ^ (0 & 010) = 010 twoOnes = 0 | (010 & 001) = 0 oneOnes = 001 ^ 010 = 011

此时所有元素处理完毕，oneOnes比特位对应的1恰好就是只重复一次的元素3对应比特位上的1，也就是oneOnes对应的值就是只重复1次元素的值。我们遍历数组所有元素，执行上面算法后就可以得到只重复1次的元素值，由于算法只需遍历一次数组，同时没有分配任何新内存，因此时间复杂度是O(n),空间复杂度是O(1)。我们看看完整实现代码:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

public class Searching {
    int extractOneTimeElement(int[] threeTimesArray) {
        //分别用于记录只出现1次的比特位和2次的比特位
        int  oneOnes = 0;
        int  twoOnes = 0;

        for (int i = 0; i < threeTimesArray.length; i++) {
            int E = threeTimesArray[i];
            int T = twoOnes; 
            int O = oneOnes;
            twoOnes = T ^ (T & E); //去除那些出现过三次的比特位1
            E = E ^ (T & E); //去除出现过3次的比特位1
            twoOnes = twoOnes | (E & O); //设置出现两次的比特位1
            oneOnes = O ^ E; //设置只出现1次的比特位1
        }

        return oneOnes;
    }

     public static void main(String[] args) {
        int[] A = new int[]{2, 2, 2, 4, 7, 11, 4, 4, 5,5,5, 7,7, 9,9,9};
        Searching s = new Searching();
        int oneTimeElement = s.extractOneTimeElement(A);
        System.out.println("The one time element is : " + oneTimeElement);
     }
}

代码中初始化了一个数组，里面除了11外所有元素都重复出现3次，代码运行后输出的结果正是只从复出现1次的数值11.