寻找在数组中的元素，其中的每一个元素重复的（不是单一出现，但更多）次奇数，只有一个出现一次 [英] 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.

首先，让我们改变的问题，让一个号码出现一次和所有其他号码出现3次。

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

算法：的

Algorithm:

下面 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;  
   }  

和发生的precisely一旦元素存储在的人。这将使用 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.

说明：的

Explanation:

如果该问题是这样的：一种元素出现一次，所有其他的偶数次，那么解决办法是异或元件。其原因是， 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:

• 的人是出现恰好一次至今的所有元素的XOR
• 三三两两是已经出现的所有元素的异或完全至今两次

• 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 是数组中的下一个元素，有三种情况：

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

1. 如果这是第一次 X 已经出现，这是异或运算成的人
2. 如果这是第二次 X 已经出现，它被取出来了的人（通过再次异或它）和异或运算成三三两两
3. 如果这是第三次 X 已经出现，它被取出来了的人和三三两两。

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.

因此​​，在最后，的人将只是一个元素的异或，即不重复的寂寞元素。有5行code，我们需要看明白为什么这个工程：后五 X = A [1]

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 已经出现，那么那些与放大器，X =那些让三三两两保持不变。该行的人^ = X; 异或 X 与的人如权利。因此 X 是在的人和三三两两只有一个，所以什么也没有发生在过去的三线为的人或三三两两。

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 已经出现，那么的人已有 X （通过上面的解释），所以现在三三两两与行三三两两得到它| =那些和放大器; X; 。此外，由于的人的 X ，行的人^ = X; 删除 X 从的人（因为 X ^ X = 0 ）。再次，最后三行什么也不做，因为对的人只有一个和三三两两现在有 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 已经出现，那么的人没有 X ，但三三两两一样。因此，第一行让我们三三两两继续 X 第二添加 X 到的人。现在，因为两个的人和三三两两有 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.

概括：的

Generalization:

如果一些数据出现5次，则该算法仍然有效。这是因为第四次 X 出现，它是在没有的人和三三两两。前两行，然后添加 X 到的人，而不是三三两两最后三行什么也不做。第五届时间 X 出现，它是在的人而不是三三两两。第一行添加到三三两两，第二个从的人删除它，最后三行什么也不做。

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 出现，它是从的人和三三两两，所以它被添加回的人 7号通。我试图想出一个聪明的方式，prevent这一点，但到目前为止，我来了空。

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屋！