找到了一些与偶数出现的 [英] Find a number with even number of occurrences

问题描述

鉴于阵列除了一个号码，其出现次数为偶数，其中出现每个数字的个数为奇数。查找与连发生的次数。

Given an array where number of occurrences of each number is odd except one number whose number of occurrences is even. Find the number with even occurrences.

例如。

1, 1, 2, 3, 1, 2, 5, 3, 3

输出应该是：

Output should be:

2

以下是限制：

The below are the constraints:

1. 在数字是不在范围内。
2. 请其原地。
3. 必需的时间复杂度为O（N）。
4. 在阵列可能包含负数。
5. 在数组排序。

通过上面的限制，我所有的想法失败：基于比较的排序，计数排序，BST的，哈希，蛮力

With the above constraints, all my thoughts failed: comparison based sorting, counting sort, BST's, hashing, brute-force.

我很好奇地想知道：这里将异或工作？如果是的话，怎么办？

I am curious to know: Will XORing work here? If yes, how?

推荐答案

这个问题一直占据着我的地铁乘坐了好几天。这里是我的想法。

This problem has been occupying my subway rides for several days. Here are my thoughts.

如果A.韦伯是对的，这个问题来自一个采访或者是某种学术上的问题，我们应该考虑的（错误）假设我们正在，也许尝试探索一些简单的情况。

If A. Webb is right and this problem comes from an interview or is some sort of academic problem, we should think about the (wrong) assumptions we are making, and maybe try to explore some simple cases.

这是浮现在脑海中的两个极端的子问题有以下几种：

The two extreme subproblems that come to mind are the following:

• 该数组包含的两个值：其中一个是重复的偶数次，而另一个被重复的次数为奇数
• 在该数组包含的 N-1不同的值：所有的值是present一次，除了一个值，该值是present两次
。

• The array contains two values: one of them is repeated an even number of times, and the other is repeated an odd number of times.
• The array contains n-1 different values: all values are present once, except one value that is present twice.

也许我们应该通过不同的值数的复杂性分开的情况下。

Maybe we should split cases by complexity of number of different values.

如果我们假设的不同值的数量为O（1），每个阵列将有 M 不同的值，用 M 独立于 N 。在这种情况下，我们可以通过原始数组循环擦除和计数出现的每个值。在这个例子中，将给予

If we suppose that the number of different values is O(1), each array would have m different values, with m independent from n. In this case, we could loop through the original array erasing and counting occurrences of each value. In the example it would give

1, 1, 2, 3, 1, 2, 5, 3, 3 -> First value is 1 so count and erase all 1
2, 3, 2, 5, 3, 3 -> Second value is 2, count and erase
-> Stop because 2 was found an even number of times.

这样就解决了的复杂度为O（MN），其计算结果为 0在第一个极端的例子（ N）。

This would solve the first extreme example with a complexity of O(mn), which evaluates to O(n).

还有更好的：如果不同值的数量是 O（1），我们可以计算哈希映射内在价值出场，读取整个阵列后，通过他们去和返回出现偶数倍一体。这woud仍然被认为 O（1）内存。

There's better: if the number of different values is O(1), we could count value appearances inside a hash map, go through them after reading the whole array and return the one that appears an even number of times. This woud still be considered O(1) memory.

在第二个极端的例子将包括在寻找一个数组中唯一的重复值。 这 O（N）似乎是不可能，但也有特殊情况，我们可以：如果数组有 N 元素和价值观里面是 {1，N-1} +重复的值（或某些变种类似的 X和Y之间的所有数字的）。在这种情况下，我们的之所有的值，substract N（N-1）/ 2 的总和，并检索重复的值。

The second extreme case would consist in finding the only repeated value inside an array. This seems impossible in O(n), but there are special cases where we can: if the array has n elements and values inside are {1, n-1} + repeated value (or some variant like all numbers between x and y). In this case, we sum all the values, substract n(n-1)/2 from the sum, and retrieve the repeated value.

解决第二个极端的情况下，与阵列，或一般情况下， M 不是恒定的内随机n值，在不断的记忆和 O（N）的时间似乎是不可能给我。

Solving the second extreme case with random values inside the array, or the general case where m is not constant on n, in constant memory and O(n) time seems impossible to me.

特注：在这里，异或不工作，因为我们想要的号码出现偶数的时间和其他出现的次数为奇数。如果问题是给出现一个的奇的数目的次数，所有其它号码出现一个的甚至的次数，我们可以XOR所有值和找到的奇一个是在末端。

Extra note: here, XORing doesn't work because the number we want appears an even number of times and others appear an odd number of times. If the problem was "give the number that appears an odd number of times, all other numbers appear an even number of times" we could XOR all the values and find the odd one at the end.

我们可以尝试来寻找使用这种逻辑的方法：我们将需要类似的函数，施加上的次数为奇数将产生0，而偶数的次将身份。不要以为这是可能的。

We could try to look for a method using this logic: we would need something like a function, that applied an odd number of times on a number would yield 0, and an even number of times would be identity. Don't think this is possible.

这篇关于找到了一些与偶数出现的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！