假设数组的整数在1到1,000,000之间.
我知道解决这个问题的一些流行方法:
我最近遇到了另一个解决方案,我需要一些帮助来理解它背后的逻辑:
保留一个基数累加器.您使用索引和该索引处的值进行异或或累加器.
x ^ C ^ x == C这个事实在这里是有用的,因为每个数字将被xor'd两次,除了那里的两次,这将出现3次.(x ^ x ^ x == x)最终索引,将出现一次.因此,如果我们使用最终索引对累加器进行种子处理,则累加器的最终值将是列表中的数字两次.
如果有人能够帮助我理解这种方法背后的逻辑,我会很感激(用一个小例子!).
假设你有一个累加器
int accumulator = 0;
在循环的每个步骤中,使用i和XOR累加器v,其中i是循环迭代的索引,并且v是i数组的第th个位置的值.
accumulator ^= (i ^ v)
通常,i并且v将是相同的数字,所以你最终会做
accumulator ^= (i ^ i)
但是i ^ i == 0,这将最终成为一个无操作,累加器的价值将保持不变.此时我应该说数组中数字的顺序无关紧要,因为XOR是可交换的,所以即使数组被混洗开始,结尾处的结果仍然应该是0(累加器的初始值).
现在如果一个数字在数组中出现两次怎么办？显然,这个数字在XORing中会出现三次(一个用于索引等于数字,一个用于数字的正常外观,一个用于额外外观).此外,其他一个数字只会出现一次(仅适用于其索引).
此解决方案现在假设仅出现一次的数字等于数组的最后一个索引,或者换句话说:数组中的数字范围是连续的并且从要处理的第一个索引开始(编辑:感谢caf提出这个单挑评论,这就是我真正想到的,但是在撰写时我完全搞砸了).有了这个(N只出现一次)作为给定,考虑从开始
int accumulator = N;
N在XORing中有效地再次出现两次.在这一点上,我们留下的数字只出现两次,只有一次出现三次.由于两次出现的数字将XOR输出为0,因此累加器的最终值将等于出现三次的数字(即一次额外).