经典算法题1：找出数组中只出现一次的数字，其它数字都出现了两次

136 阅读 0 评论 90 点赞

我是靠谱客的博主幸福犀牛，这篇文章主要介绍经典算法题1：找出数组中只出现一次的数字，其它数字都出现了两次，现在分享给大家，希望可以做个参考。

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

题解

其它数字都出现了两次，只有一个数出现了一次。可以想到运用异或运算，任何一个数字异或它自己都等于0。

样例：2 3 4 2 3
所有数字依次异或运算：2 xor 3 xor 4 xor 2 xor 3 = (2 xor 2) xor (3 xor 3) xor 4= 0 xor 0 xor 4 = 4
最终结果4就是我们要找的那个只出现一次的数字。

复制代码

1
2
3
4
5
6
7
8
9
void FindNumsAppearOnce(int data[], int length, int &num1)
{
if (length < 2) return;
int resultExclusiveOR = 0;
for (int i = 0; i < length; ++ i)
resultExclusiveOR = resultExclusiveOR ^ data[i];
num1 = resultExclusiveOR ;
}

此题拓展

题目： 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求： 时间复杂度是 O(n) ，空间复杂度是 O(1) 。
分析： 数组里包含了两个只出现一次的数字，那么所有数字依次异或的结果就是这两个只出现一次的数字的异或结果。
利用这个异或结果，把数组分为两个子数组，一个子数组包含一个只出现一次的数字，另一个数组包含另一个只出现一次的数字。
由于这两个只出现一次的数字肯定不相等，那么这个异或结果肯定不为 0 ，也就是说在这个结果数字的二进制表示中至少就有一位为 1 。
在结果数字中找到第一个为 1 的位的位置，记为第 N 位。以第N位是不是 1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第 N 位都为 1 ，而第二个子数组的每个数字的第 N 位都为 0 。

样例：1 2 3 4 2 3
所有数字的亦或结果 = 1 xor 4
二进制表示为：      0 0 1
                         xor 1 0 0
                       —————
                               1 0 1
异或结果的二进制位 101，第一个为 1 的位的位置 N = 1 。
那么，数组所有数的二进制表示中，第 N(N = 1) 位为 1 的的数为 1 3 3 ，第 N(N = 1) 位为0的的数为 2 2 4 。
这样就把原数组拆分为两个子数组，1 和 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
39
40
41
42
43
44
45
46
47
void FindNumsAppearOnce(int data[], int length, int &num1, int &num2)
{
if (length < 2)
return;
// get num1 ^ num2

int resultExclusiveOR = 0;
for (int i = 0; i < length; ++ i)
resultExclusiveOR ^= data[i];
// get index of the first bit, which is 1 in resultExclusiveOR

unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR);
num1 = num2 = 0;
for (int j = 0; j < length; ++ j)
{
// divide the numbers in data into two groups,

// the indexOf1 bit of numbers in the first group is 1,

// while in the second group is 0

if(IsBit1(data[j], indexOf1))
num1 ^= data[j];
else
num2 ^= data[j];
}
}
// Find the index of first bit which is 1 in num (assuming not 0)

unsigned int FindFirstBitIs1(int num)
{
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 32))
{
num = num >> 1;
++ indexBit;
}
return indexBit;
}
// Is the indexBit bit of num 1?

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