寻找数组中只出现一次的数

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。



分析：首先先来看一个稍微简单的版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。这里将会考虑到“异或”的操作：因为异或具有如下的特性：

1. 任何数值和0做异或操作，得到的结果还是本身，即A^0=A

2. 任何两个相同的数值做异或操作，得到的结果是0，即A^A=0

所以，数组中所有的数字都异或操作一遍的话，出现两次的数字都会被抵消掉，最后得到的数便是只出现一次的数字。

/**

 * 如果一个数组集合中除了一个数出现了一次，其余的数值都出现了两次， 怎么快速找出这个只出现一次的数值呢？

 * 

 * @author Eric

 * 

 */

public class FinNumber {

 

    /**

     * 考虑到如下两点：

     * 1. 任何数值和0做异或操作，得到的结果还是本身，即A^0=A

     * 2. 任何两个相同的数值做异或操作，得到的结果是0，即A^A=0

     * 

     * 数组中所有的数字异或操作一遍之后得到的数字就是只出现一次的数字。

     */

    public int find(int[] data) {

       int result = 0;

       for (int value : data) {

           result ^= value;

       }

       return result;

    }

 

    public static void main(String[] args) {

       FinNumber fn = new FinNumber();

       int[] data = new int[]{1,5,3,2,1,5,3};

       System.out.println(fn.find(data));

       

    }

}

现在再来看一下，怎么查找两个只出现一次的数字。

思路就是将数组分成两个部分：还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。在结果数字中找到第一个为1的位的位置，记为第N位。现在以第N位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N位都为1，而第二个子数组的每个数字的第N位都为0。

根据这种思想，写出如下代码：

/**

 * 首先来看题目要求：

 * 

 * 在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找出这两个数字

 * 

 * @author Eric

 * 

 */

 

public class FindTwoNoRepeatNumbers {

 

    public void process(int[] data) {

 

       /**

        * 1. 异或整个数组，

        */

       int xor = populateXORValue(data);

 

       /**

        * 2. 根据整个数组异或得到的值，判断哪一位(低位到高位,0开始计算)要进行区别 0 或者1

        */

 

       int position = populatePosition(xor);

 

       /**

        * 3. 根据不同位置上的值是0还是1区别不同的数组

        */

       int[] numbers = populateNoRepeatNumnbers(data, position);

 

       /**

        * 4. 打印出只出现一次的两个数字

        */

       printTwoNumbers(numbers);

    }

 

    private int[] populateNoRepeatNumnbers(int[] data, int position) {

       int num1 = 0, num2 = 0;

       for (int i = 0; i < data.length; ++i) {

           if (((data[i] >> position) & 1) == 1)

              num1 ^= data[i];

           else

              num2 ^= data[i];

       }

       return new int[] { num1, num2 };

    }

 

    private int populateXORValue(int[] data) {

       int xor = 0;

       for (int element : data) {

           xor ^= element;

       }

       return xor;

    }

 

    private int populatePosition(int xorValue) {

       int position = 0;

       while ((xorValue & 1) == 0) {

           xorValue >>= 1;

           position++;

       }

       return position;

    }

 

    private void printTwoNumbers(int[] numbers) {

       System.out.println(String.format("数组中只出现一次的两个数字是: %d, %d", numbers[0],

              numbers[1]));

    }

 

    public static void main(String[] args) {

       FindTwoNoRepeatNumbers util = new FindTwoNoRepeatNumbers();

       util.process(new int[] { 1, 3, 3, 1, 5, 8 });

       util.process(new int[] { 1, 3, 6, 3 });

    }

}

输出结果：

数组中只出现一次的两个数字是: 5, 8

数组中只出现一次的两个数字是: 1, 6