在数组中查找每个元素重复奇数次(但不止一次)并且只有一个元素出现一次的元素 [英] Finding an element in an array where every element is repeated odd number of times (but more than single occurrence) and only one appears once

问题描述

您有一个数组，其中每个数字都重复奇数次(但不止一次).恰好一个数字出现一次.怎么找到只出现一次的数字?

You have an array in which every number is repeated odd number of times (but more than single occurrence). Exactly one number appears once. How do you find the number that appears only once?

e.g.: {1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3}

答案是 9.

我正在考虑创建一个哈希表，然后只计算计数为 1 的元素.这似乎微不足道，我没有使用这样一个事实，即每个其他元素都会重复奇数次.有没有更好的方法.

I was thinking about having a hash table and then just counting the element whose count is 1. This seems trivial and i am not using the fact that every other element is repeated an odd no of times. Is there a better approach.

推荐答案

相信你仍然可以巧妙地运用 XOR 的基本思想来解决这个问题.

I believe you can still use the basic idea of XOR to solve this problem in a clever fashion.

首先，让我们改变问题，一个数字出现一次，所有其他数字出现三次.

First, let's change the problem so that one number appears once and all other numbers appear three times.

算法:

这里A是长度为n的数组:

   int ones = 0;  
   int twos = 0;  
   int not_threes, x;  

   for (int i=0; i<n; ++i) {  
            x =  A[i];  
            twos |= ones & x;  
            ones ^= x;  
            not_threes = ~(ones & twos);  
            ones &= not_threes;  
            twos &= not_threes;  
   }  

并且恰好出现一次的元素存储在ones中.这使用 O(n) 时间和 O(1) 空间.

And the element that occurs precisely once is stored in ones. This uses O(n) time and O(1) space.

我相信我可以将这个想法扩展到该问题的一般情况，但你们中的一个人可能可以做得更快，所以我现在暂时搁置这个，并在我可以概括解决方案时对其进行编辑.

I believe I can extend this idea to the general case of the problem, but possibly one of you can do it faster, so I'll leave this for now and edit it when and if I can generalize the solution.

解释:

如果问题是这样的:一个元素出现一次，所有其他元素出现偶数次"，那么解决方案是对元素进行异或.原因是x^x = 0，所以所有配对的元素都会消失，只留下孤独的元素.如果我们在这里尝试相同的策略，我们将剩下不同元素的异或，这不是我们想要的.

If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.

相反，上述算法执行以下操作:

Instead, the algorithm above does the following:

• ones 是到目前为止只出现过一次的所有元素的异或
• twos 是到目前为止恰好出现两次的所有元素的异或

• ones is the XOR of all elements that have appeared exactly once so far
• twos is the XOR of all elements that have appeared exactly twice so far

每次我们取x作为数组中的下一个元素，有3种情况:

Each time we take x to be the next element in the array, there are three cases:

1. 如果这是第一次出现 x，它会被异或到 ones
2. 如果这是第二次 x 出现，它会从 ones 中取出(通过再次异或)并异或到 twos
3. 如果这是第三次出现 x，则从 ones 和 twos 中取出.

1. if this is the first time x has appeared, it is XORed into ones
2. if this is the second time x has appeared, it is taken out of ones (by XORing it again) and XORed into twos
3. if this is the third time x has appeared, it is taken out of ones and twos.

因此，最后，ones 将只是一个元素的异或，即不重复的孤独元素.我们需要查看 5 行代码来了解其工作原理:x = A[i] 之后的 5 行.

Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].

如果这是第一次出现 x，那么 ones&x=ones 所以 twos 保持不变.行 ones ^= x; XORs x 与 ones 声称.因此 x 正好是 ones 和 twos 之一，所以最后三行到 ones 没有任何反应或 twos.

If this is the first time x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed. Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos.

如果这是第二次出现 x，那么 ones 已经有 x(根据上面的解释)，所以现在 twos 使用 twos |=ones & 行获取它x;.另外，由于 ones 有 x，所以 ones ^= x; 行从 ones<中删除了 x/code>(因为 x^x=0).再一次，最后三行什么都不做，因为 ones 和 twos 之一现在有 x.

If this is the second time x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes x from ones (because x^x=0). Once again, the last three lines do nothing since exactly one of ones and twos now has x.

如果这是 x 第三次出现，那么 ones 没有 x 但 twos 有.所以第一行让 twos 保留 x，第二行将 x 添加到 ones.现在，由于 ones 和 twos 都有 x，最后三行从两者中删除 x.

If this is the third time x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones. Now, since both ones and twos have x, the last three lines remove x from both.

概括:

如果某些数字出现了 5 次，那么这个算法仍然有效.这是因为第 4 次出现 x 时，它既不是 ones 也不是 twos.前两行然后将 x 添加到 ones 而不是 twos 并且最后三行什么都不做.第 5 次出现 x 时，它在 ones 但不是 twos.第一行将它添加到 twos 中，第二行将它从 ones 中删除，最后三行什么都不做.

If some numbers appear 5 times, then this algorithm still works. This is because the 4th time x appears, it is in neither ones nor twos. The first two lines then add x to ones and not twos and the last three lines do nothing. The 5th time x appears, it is in ones but not twos. The first line adds it to twos, the second removed it from ones, and the last three lines do nothing.

问题是第6次出现x，取自ones和twos，所以又加回ones 在第 7 次通过.我试图想出一个聪明的方法来防止这种情况发生，但到目前为止我是空的.

The problem is that the 6th time x appears, it is taken from ones and twos, so it gets added back to ones on the 7th pass. I'm trying to think of a clever way to prevent this, but so far I'm coming up empty.

这篇关于在数组中查找每个元素重复奇数次(但不止一次)并且只有一个元素出现一次的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！