logo标签列表

找出一个数字重复了偶数次，而其他所有数字都重复了奇数次

algorithm
7
给定一个整数数组。 数组中的每个数字重复出现奇数次，但只有1个数字重复出现偶数次。 找到那个数字。
我考虑使用哈希映射，记录每个元素的计数。这需要O(n)空间。是否有更好的方法？
3
因为0是偶数，所以在数组中出现偶数次的整数将无限多。 - hmakholm left over Monica
1
考虑到数字已经在数组中，你只需要计算出现在数组中的数字。 - Aleks G
5个回答
3

您不需要保留每个元素出现的次数 - 只需要知道它出现的次数是偶数还是奇数 - 所以每个元素只需要1位。对于每个元素，一开始都是0，当遇到该元素时，将相应的位翻转。下次遇到它时，再次翻转该位。最后，只需检查哪个位是1。

正如您所说，数字应该是有界的，例如如果一个数字是2^30，那么您应该有一个大小为2^30的列表，这并不好（这是跳表和计数排序的想法，但没有边界是行不通的）。 - Saeed Amiri
3
哈希表没问题，但你只需要存储每个元素的计数模2。所有这些计数最终都会成为1(奇数)，除了0(偶数) - 计数元素。
（正如Aleks G所说，您不需要使用算术(count++%2)，只需要使用异或(count^= 0x1); 尽管任何编译器都会优化它。）
1
显然，有一个O(n)时间和O(1)空间的解决方案。请参见此处：http://www.careercup.com/question?id=5707243546738688 -- 看起来可以使用异或运算完成。有什么想法吗？我一直在思考，但到目前为止还没有头绪！！ - Myna
@Myna，请将其发布为答案！ - smci
3

我不知道“repeat”这个词的意思，但如果有(all-1)个数字出现了偶数次，只有一个数字出现了奇数次，那么XOR就可以解决问题。

没错。只需对所有内容执行按位异或操作即可。 - Svante
你是故意回答不同的问题，还是误读了？ - gsgx
@gsingh2011：不是。这是关于语言的问题。一个出现了N次的数字会被重复N-1次。（第一次出现不算重复，第二次才是）。 - wildplasser
1

如果所有数字都重复偶数次，只有一个数字重复了奇数次，那么如果你对所有数字进行XOR运算，就能找到重复奇数次的数字。

根据您目前的陈述，我认为哈希表是一个好主意，但我会思考一下以找到更好的方法。（这是针对正整数的）

不是我给你点踩，但你把问题描述反了。只有一个数字重复了偶数次，而不是奇数次。 - Chris Mennie
@Chris Mennie，我没有把它反转，我是说如果是这样的话可以用这种方法来完成，但对于当前的问题陈述，除了哈希映射之外，我没有任何想法，我在我的答案中提到了这一点。我只是为了帮助OP，如果他也有相反的情况。 - Saeed Amiri
很好，我同意你所说的。反问题更容易解决。 - Chris Mennie
0

显然，有一个O(n)时间和O(1)空间的解决方案，因为这是在一个软件工程师公司明确提出的限制条件。请参见此处：Bing面试问题 -- 看起来可以使用数组中的数字进行异或运算来完成。祝你好运！:)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接