【面试题040】数组中只出现一次的数字

【面试题040】数组中只出现一次的数字

题目：

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

思路一：

考虑，只有一个元素出现一次的情况，任何一个数字异或自己都得0，

也就是说我们从头到位异或每个元素，那么最后得到的就是那个出现一次的。

思路二：

能不能想办法把原来的数组分成两个数组，使每个数组中有一个元素只出现过一次。

我们还是重头到位异或每个袁术，那么最后得到的就是那两个不同的元素的异或，

因为其不为0，那么其至少有一位为1

1 ^ 0 = 1

0 ^ 1 = 1

——那么我们就以这个为1的这一位是不是0，把原来的数组分成两个子数组。

因为两个相同的数字的任意一位都是相同的，所以，它们肯定去了同一个子数组。

那么再利用思路一就找出来了两个只出现一次的数字啦。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>

using namespace std;

bool IsBit1(int num, unsigned int indexBit)
{
    num = num >> indexBit;
    return (num & 1);
}

unsigned int FindFirstBitIs1(int num)
{
    int indexBit = 0;
    while ( ((num & 1) == 0) && (indexBit < 8 * sizeof(int)) )
    {
        num = num >> 1;
        ++ indexBit;
    }
    return indexBit;
}

void FindNumsAppearOnce(int data[], int length, int *num1, int *num2)
{
    if (data == NULL || length < 2)
    {
        return ;
    }
    int resultExclusiveOR = 0;
    for (int i = 0; i < length; ++i)
    {
        resultExclusiveOR ^= data[i];
    }

    unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);

    *num1 = *num2 = 0;
    for (int j = 0; j < length; ++j)
    {
        if (IsBit1(data[j], indexOf1))
        {
            *num1 ^= data[j];
        }
        else
        {
            *num2 ^= data[j];
        }
    }
}

int main()
{
    int data[] = {2, 4, 3, 6, 3, 2, 5, 5};
    int length = sizeof(data) / sizeof(data[0]);
    int num1, num2;
    FindNumsAppearOnce(data, length, &num1, &num2);
    cout << num1 << " " << num2 << endl;
    return 0;
}