找到一个整数，发生频率，即使在整数的特定阵列时，所有其他人出现奇怪的频率 [英] Find a single integer that occurs with even frequency in a given array of ints when all others occur odd with frequency

问题描述

这是一个面试问题。

鉴于整数数组，发现其发生与偶数频率数组中的一个整数值。所有整数将为正。其他所有的数字出现奇怪的频率。数组中的最大数可以INT_MAX。

Given an array of integers, find the single integer value in the array which occurs with even frequency. All integers will be positive. All other numbers occur odd frequency. The max number in the array can be INT_MAX.

例如，[2,8，6,2]应返回2

For example, [2, 8, 6, 2] should return 2.

原来阵列可以被修改，如果你能找到更好的解决方案，如O（1）O（n）的时间空间。

the original array can be modified if you can find better solutions such as O(1) space with O(n) time.

我知道如何通过哈希表来解决这个问题（遍历和计数频率）。这是O（n）的时间和空间。

I know how to solve it by hashtable (traverse and count freq). It is O(n) time and space.

是否有可能被O解决（1）空间或更好的时间？

Is it possible to solve it by O(1) space or better time?

推荐答案

由于这是一个面试问题，答案是：O（1）空间是可以实现为1非常大的价值：

Given this is an interview question, the answer is: O(1) space is achievable "for very big values of 1":

• prepare所有0
的matcharray 1..INT_MAX
• 当遍历数组，使用整数作为索引，matcharray，加入1
• 在完成后，遍历数组匹配，找到一个条目，正偶数值

• Prepare a matcharray 1..INT_MAX of all 0
• When traversing the array, use the integer as an index into the matcharray, adding 1
• When done, traverse the match array to find the one entry with a positive even value

这个空间很大，但独立的输入数组的大小，所以O（1）空间。对于真正的大数据集（说小的数值范围，但是巨大的数组长度），这甚至可能是一个实际有效的解决方案。

The space for this is large, but independent of the size of the input array, so O(1) space. For really big data sets (say small value range, but enormous array length), this might even be a practically valid solution.

这篇关于找到一个整数，发生频率，即使在整数的特定阵列时，所有其他人出现奇怪的频率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！