如何在混洗连续整数数组中找到重复元素？

Question

我最近在某个地方遇到过一个问题:

假设您有一个1001整数的数组.整数是随机顺序,但您知道每个整数在1到1000之间(包括1和1000).此外,每个数字在数组中只出现一次,但一个数字除外,它出现两次.假设您只能访问数组的每个元素一次.描述一个算法来查找重复的数字.如果您在算法中使用了辅助存储,是否可以找到不需要它的算法？

我感兴趣的是第二部分,即不使用辅助存储.你有什么主意吗？

Answer 1

只需将它们全部添加起来,如果只使用了1001个数字,则减去所期望的总数.

例如:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Answer 2

更新2:有些人认为使用XOR查找重复的数字是一个黑客或技巧.我的官方回应是:"我不是在寻找一个重复的数字,我正在寻找一组位集中的重复模式.而XOR绝对比ADD更适合操作位集".:-)

更新:在我上床睡觉之前,这里的"一线"替代解决方案需要零额外存储(甚至不是循环计数器),每次触摸每个数组元素一次,非破坏性且根本无法扩展: - )

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

请注意,编译器实际上会在编译时计算该表达式的后半部分,因此"算法"将在1002个操作中执行.

如果在编译时也知道数组元素值,编译器会将整个语句优化为常量.:-)

原始解决方案:哪些不符合问题的严格要求,即使它能找到正确的答案.它使用一个额外的整数来保持循环计数器,并且它访问每个数组元素三次 - 两次读取它并在当前迭代中写入它并且一次读取它以用于下一次迭代.

那么,在通过数组时,至少需要一个额外的变量(或CPU寄存器)来存储当前元素的索引.

除此之外,这里是一个破坏性算法,可以安全地扩展任何N到MAX_INT.

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

Answer 3

Franci Penov的非破坏性解决方案.

这可以通过使用XOR操作员来完成.

让我们说我们有一个大小的数组5:4, 3, 1, 2, 2
哪个在索引:                        0, 1, 2, 3, 4

现在做一个XOR所有元素和所有索引.我们得到2,这是重复的元素.发生这种情况是因为,0在XORing中没有任何作用.其余的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基础解决方案:)

这使用了一个额外的变量,因此完全不符合问题的要求.

Answer 4

将所有数字加在一起.最终总和将是1 + 2 + ... + 1000 +重复数字.

Answer 5

解释弗朗西斯·佩诺夫的解决方案.

(通常)问题是:给定一个任意长度的整数数组,它只包含重复偶数次的元素,除了一个重复奇数倍的值,找出这个值.

解决方案是:

acc = 0
for i in array: acc = acc ^ i

你目前的问题是改编.诀窍是你要找到重复两次的元素,这样你就需要调整解决方案来弥补这个怪癖.

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

弗朗西斯的解决方案到底是做什么的,尽管它会摧毁整个阵列(顺便说一下,它只会破坏第一个或最后一个元素......)

但是因为你需要为索引提供额外的存储空间,所以如果你还使用额外的整数,我认为你会被原谅......这种限制很可能是因为他们想要阻止你使用数组.

如果他们需要O(1)空间(1000可以被视为N,因为它在这里是任意的),它会更准确地措辞.

Answer 6

添加所有号码.整数1..1000的总和是(1000*1001)/ 2.与你得到的不同的是你的号码.