【剑指Offer】数组中只出现一次的数字

Posted on | In ,

题目

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

实现

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
public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
    if (array == null || array.length < 2)
        return;

    int result = 0;

    for (int i = 0; i < array.length; i++)
        result ^= array[i];

    int index = findFirstBitIsOne(result);

    for (int i = 0; i < array.length; i++) {
        if (isBitOne(array[i], index))
            num1[0] ^= array[i];
        else
            num2[0] ^= array[i];
    }
}

private int findFirstBitIsOne(int result) {
    int index = 0;

    while (index < 32 && (result & 1) == 0) {
        result >>= 1;
        index++;
    }

    return index;
}

private boolean isBitOne(int num, int index) {
    num >>= index;
    return (num & 1) == 1 ;
}