剑指offer面试题

题目

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

思路

这道题，初看完全没有思路。直到看了剑指offer上面的提示，才知道原来是这么回事儿。

真心叹服里面的解法。

首先思考一个问题：假如一个整型数组里面只有一个数字出现了一次，怎么找？

书中用到的思路：异或。

因为异或有这样一个性质：A^0=A; A^A=0;

除此之外，更重要的就是它满足交换律和结合律。

比如 [A B C B A C D]数组：0^A^B^C^B^A^C^D = (A^A^B^B^C^C^D) = D.

所以利用这种思路，就可以最快找出只出现一次的数字。

那么，有两个数字出现了一次怎么办？

有了上面的思路作为铺垫，可以想到，如果能把这两个数字分到两组就好了，接下来只要对每组用上面的方法就可以求出来了。

怎么分？

这才是这道题的难点所在。

书中的思路：因为如果有两个只出现了一次且不一样的数字，则按照上面的异或思路，最终结果一定不为0.如果不为0，则一定至少有一位是1.

因为其他数字都被异或为0，只有这两个数字剩下，且异或非零。那么这两个数字的相应位上，一定一个是0，一个是1（如果都是0或者都是1，则异或为0）。而这就是分组的关键。

只要把异或结果中二进制形式 1 在第几位求出来，然后按照该位上是否为1分为两组。这样一定能确保这两个数被分在不同的两组中。

疑问：会不会把一对一样的数字分在两个组里面呢？很显然不会。因为这两个数字的每一位都一样，要么为 0，要么为1，必定会在一组中。

看到这里，就两个字：服了。

思路明白，剩下的就是实现的问题了。这里有一个小技巧，刚开始我想设计两个数组，然后存放按照位分开的数字，但是这种做法的空间复杂度就不是O(1)了。必须另想办法，书中的一种办法是：直接拿来异或就行了，反正最终要的就是该组剩下的那个数字。所以，只要把这两个数字返回就行了。

代码

package com.ans;

//数组中只出现了一次的数字
public class Solution8 {
    public static void seperateArr(int[] retArr, int[] arr) {
        int result = 0;
        for (int data : arr) {
            result ^= data;
        }

        if (result == 0) {
            System.out.println("输入的数组不满足条件");
            return;
        }

        int bit = 0;// 第一个不为0的位

        while (result % 2 == 0) {
            bit++;
            result /= 2;
        }

        for(int i = 0; i < arr.length; i++) {
            if(bitIs1(arr[i], bit)) {
                retArr[0] ^= arr[i];
            } else {
                retArr[1] ^= arr[i];
            }
        }
    }

    //判断整数num的bit位是不是1
    public static boolean bitIs1(int num, int bit) {
        num >>>= bit;
        return num % 2 == 1;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 1, 8, 7, 7, 3, 3, 4, 5, 4, 5, 6 };
        int[] result = new int[2];// save the two numbers
        seperateArr(result, arr);
        System.out.println("第一个数字是：" + result[0] + ",第二个数字是：" + result[1]);
    }
}