数组中只出现一次的数字

发表于   |  

题目

一个整型数组里除了两个数字之外，其他的数字都出现两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O（1）。
{2，4，3，6，3，2，5，5} 结果为4，6。

异或运算的特性

  1. 交换律 a^b = b^a
  2. 结合律 a^b^c = a^(b^c)
  3. a^a = 0
  4. 0^a = a
  5. a^b^a = a^a^b = b
  6. 如果a^b = 1 != 0，则a与b的二进制形式的个位是不相同的

结题思路

只有一个数字只出现一次

题目如果改为只有一个出现一次的数字。
根据特性5，我们只需要把所有的数字一起异或就会得到这个只出现一次的数字N.
N = 0^A[0]^A[1]^A[2]….

两个数字只出现一次

1) x = n^m = 0^A[0]^A[1]^A[2]….
根据特性6我们知道如果n,m不相等.他们异或的结果的二进制形式的每一位都代表n，m二进制对应位不相同。例如两个二进制数字a,b异或：10011^11011 = 1000 , 二进制结果中只有第四位数字等于1，则a，b的第四位不同。
2）挑选所有元素异或结果x的其中一个为1的位置不变，其他位置变为0，得到y.假设x的二进制形式为10110，y=10000.
3）每个元素与y进行与运算，结果为等于y的是一组，结果不为y的是一组。n和m一定不在同一组。
4）问题转化为只有一个数字只出现一次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class TestXor {
    public static int getArrXorResult(int[] arr, int begin, int end) {
        int result = 0;
        for (int i = begin; i < end; i++) {
            result ^= arr[i];
        }
        return result;
    }

    public static int getXOne(int x) {
        int l = 0;
        for (l = 0; x >> 1 != 0; l++) {
            x >>= 1;
        }
        return 1 << l;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 4, 5, 2, 3, 4, 6};
        //分别装载两个分组
        int[] arr0 = new int[arr.length];
        int[] arr1 = new int[arr.length];
        int x = getArrXorResult(arr, 0, arr.length);
        //获取异或结果二进制结果是1的最大的那个
        int y = getXOne(x);
        int index0 = 0, index1 = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & y) == y) {
                arr0[index0++] = arr[i];
            } else {
                arr1[index1++] = arr[i];
            }
        }
        int n = getArrXorResult(arr0, 0, index0);
        int m = getArrXorResult(arr1, 0, index1);
        System.out.println("n=" + n + " m=" + m);
    }
}