<分区>
我能想到的是:
算法:
- 有一个哈希表来存储数字及其相关计数
- 解析数组并增加数字的计数。
- 现在解析哈希表以获取计数为 1 的数字。
你们能想出比这更好的解决方案吗？ 使用 O(n) 运行时间且不使用额外空间
<分区>
我能想到的是:
算法:
你们能想出比这更好的解决方案吗？ 使用 O(n) 运行时间且不使用额外空间
最佳答案
假设您可以对数字进行XOR，我相信这就是这里的关键，因为具有以下属性:
XOR 是交换律和结合律(因此执行顺序无关紧要)。异或的数字将始终为零。XOR运算就是那个数字。因此，如果您简单地将所有值异或在一起，所有出现两次的值将相互抵消(给出 0)，剩下的一个数(n) 将 XOR 与该结果 (0) 给出 n。
r = 0
for i = 1 to n.size:
r = r xor n[i]
print "number is " + r
不需要哈希表，它具有 O(n) 的性能和 O(1) 的额外空间(只是一个很小的整数)。
关于给定所有其他数字出现两次，查找在数组中仅出现一次的数字的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1089987/