假设你有一个包含1001个整数的数组。这些整数是随机排列的,但你知道每个整数都在1到1000(含)之间。此外,每个数字仅出现一次,除了一个数字出现两次。假设你只能访问数组的每个元素一次,请描述一种算法来找到重复的数字。如果你的算法使用了辅助存储器,你能否找到不需要它的算法?
我感兴趣的是要知道第二部分,即不使用辅助存储的方法。你有任何想法吗?
把它们全部加起来,然后从中减去如果只使用1001个数字时你所期望的总和。
例如:
Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10
Input - Expected => 2
更新2: 有些人认为使用异或运算符寻找重复数字是一种黑客行为或技巧。我的官方回答是:“我不是在寻找重复数字,而是在寻找位集数组中的重复模式。而异或运算符绝对比加法更适合操作位集。”
更新: 在我睡觉前,只是为了好玩,这里有一个“一行代码”的替代解决方案,它需要零额外存储(甚至没有循环计数器),只触及每个数组元素一次,是非破坏性的,但根本不可扩展 :-)
printf("Answer : %d\n",
array[0] ^
array[1] ^
array[2] ^
// continue typing...
array[999] ^
array[1000] ^
1 ^
2 ^
// continue typing...
999^
1000
);
请注意,编译器实际上会在编译时计算该表达式的后半部分,因此“算法”将在确切的1002个操作中执行。for (int i = 1; i < 1001; i++)
{
array[i] = array[i] ^ array[i-1] ^ i;
}
printf("Answer : %d\n", array[1000]);
我会留给你自己去思考为什么这个方法有效,但是给你一个简单的提示:-)
a ^ a = 0
0 ^ a = a
Franci Penov的解决方案的非破坏性版本。
可以通过使用 XOR
运算符来实现。
假设我们有一个大小为5
的数组:4, 3, 1, 2, 2
它们在索引位置上分别是: 0, 1, 2, 3, 4
现在对所有元素和所有索引进行XOR
运算。我们得到2
,这就是重复的元素。这是因为0
没有参与XOR运算。剩下的n-1
个索引和数组中相同的n-1
个元素配对,数组中唯一没有配对的元素将是重复的元素。
int i;
int dupe = 0;
for(i = 0; i < N; i++) {
dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.
该解决方案最好的特点是它不会遇到基于加法的解决方案中出现的溢出问题。
由于这是一道面试题,最好从基于加法的解决方案开始,识别溢出限制,然后给出基于XOR
的解决方案:)
这种方法使用了一个额外的变量,因此并不完全符合问题要求。
{ 1043, 1042, 1044, 1042 }
,通过与{ 0,1042,1043,1044 }
进行异或运算,同样可以实现。 - legends2k将所有数字相加。最终的结果将会是 1+2+...+1000+重复的数字。
acc = 0
for i in array: acc = acc ^ i
您目前遇到的问题是一个适应性问题。关键是,您需要找到重复两次的元素,因此您需要调整解决方案以弥补这个怪癖。
acc = 0
for i in len(array): acc = acc ^ i ^ array[i]
将所有数字相加。整数1..1000的总和为(1000*1001)/2。与您得到的结果之差即为您的数字。
arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2
为什么它有效的解释在@Matthieu M.的答案中。
如果你知道我们有精确的数字1-1000,你可以将结果相加并从总数中减去500500
(sum(1, 1000)
)。这将给出重复的数字,因为sum(array) = sum(1, 1000) + repeated number
。
嗯,有一种非常简单的方法来解决这个问题...在1到1000之间的每个数字都恰好出现一次,除了重复的数字...所以,从1到1000的总和为500500。因此,算法如下:
sum = 0 对于数组中的每个元素: sum += 数组的该元素 number_that_occurred_twice = sum - 500500
n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s