来来来，看一道面试题！！！
题目是这样叙述的：
在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找出这两个数字。
要求：时间复杂度为O(N)，空间复杂度为O(1)。
这该怎么解决呢？？？
请看我的分析：
将这道题简单化：
一个数组中只有一个数字出现一次，其他数字都是成对出现的，这时我们可以根据异或运算符的特性：A^B^A = B; 0 ^ A = A；我们可以将这个数组的全部元素依次做异或运算，最终结果就是那个只出现一次的数字。
如果这个数组中出现两个不同的数字，而其他数字均出现两次，假设这两个数字分别是x, y。那如果可以将x, y分离到两个数组。这时这道题就变成两个我们简化之后的版本中的数组了。这样问题就可以得到解决了。由于x，y肯定是不相等的，因此在二进制上必定至少有一位是不同的。根据这一位是0还是1可以将x，y分开到A组和B组。并且数组中其他元素也可以根据这个方法划分到两个数组中。这时将两个数组分别做异或运算，结果就是这两个数字。
下面就看我实现的例子吧：
|
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
|
void
FindNums(
int
a[],
int
n,
int
* num1,
int
* num2)
//a[]一维数组；n是数组中的元素个数；
{
//num1和num2分别要保存两个只出现一次的数字
int
tmp = 0;
for
(
int
i = 0; i < n; i++)
{
tmp ^= a[i];
}
int
j = 0;
for
(j; j <
sizeof
(
int
)* 8; j++)
{
if
((tmp >> j) & 1 == 1)
break
;
}
num1 = 0;
num2 = 0;
for
(
int
i = 0; i < n; i++)
{
if
((a[i] >> j) & 1 == 1)
{
*num1 ^= a[i];
}
else
{
*num2 ^= a[i];
}
}
}
|
恩，问题解决了
本文转自 七十七快 51CTO博客，原文链接:http://blog.51cto.com/10324228/1787589
