在列表中查找一个数字
在列表中查找仅出现一次且所有其他数字恰好出现两次的最佳算法是什么？
因此，在整数列表(让它作为数组)中，每个整数精确地重复两次，除了一个。要找到一个，最好的算法是什么。
解决方案
回答
我们需要对某些人指定"最佳"的意思，速度才是最重要的，对于其他人来说答案就是"最佳"，如果解决方案更具可读性，它们可能会原谅几百毫秒。
除非我们更具体，否则"最佳"是主观的。
说：
遍历数字，对于每个数字，在列表中搜索该数字，当我们到达仅返回搜索结果数量1的数字时，就完成了。
回答
O(N)时间，O(N)内存
HT =哈希表
HT.clear()
按顺序查看列表
对于我们看到的每个项目
if(HT.Contains(item)) -> HT.Remove(item) else ht.add(item)
最后，HT中的项目就是我们要寻找的项目。
注意(贷方@Jared Updike)：此系统将找到所有奇数项的实例。
评论：我看不到人们如何投票给我们提供NLogN性能的解决方案。 "更好"在哪个宇宙中？
更让我们震惊的是我们标记了已接受的答案-NLogN解决方案...
但是，我确实同意，如果要求内存是恒定的，那么(到目前为止)NLogN是最好的解决方案。
回答
我想说，使用排序算法然后遍历排序列表以找到数字是一种很好的方法。
现在的问题是找到"最佳"排序算法。排序算法很多，每种算法各有优缺点，因此这是一个相当复杂的问题。 Wikipedia条目似乎是一个很好的信息来源。
回答
似乎最好的办法是遍历该列表，将每个项目添加到"已看到"的项目列表中，或者将其从"已看到"的项目中删除(如果已经存在)，最后在"已看到"列表的最后"项目将包含单数元素。关于时间，这是O(n)，关于空间，这是n(在最坏的情况下，如果对列表进行排序会更好)。
它们是整数的事实并没有真正考虑在内，因为将它们加起来并没有什么特别的事情……在那儿吗？
问题
我不明白为什么选择的答案在任何标准下都是"最佳"的。 O(N * lgN)> O(N)，它将更改列表(或者创建列表的副本，这在空间和时间上仍然更加昂贵)。我想念什么吗？
回答
我们可以简单地将集合中的元素放入哈希中，直到发现冲突为止。在红宝石中，这是单线的。
def find_dupe(array)
h={}
array.detect { |e| h[e]||(h[e]=true; false) }
end
因此，find_dupe([1,2,3,4,5,1])将返回1.
这实际上是一个常见的"技巧"面试问题。它通常是关于一个重复的连续整数列表。在这种情况下，面试官经常寻找我们使用n整数技巧的高斯和，例如从实际总和中减去" n *(n + 1)/ 2"。教科书的答案是这样的。
def find_dupe_for_consecutive_integers(array) n=array.size-1 # subtract one from array.size because of the dupe array.sum - n*(n+1)/2 end
回答
取决于数字的大小/不同。基数排序可能适用，这将在很大程度上减少O(N log N)解决方案的排序时间。
回答
最快(O(n))和内存效率最高(O(1))的方法是XOR操作。
在C中：
int arr[] = {3, 2, 5, 2, 1, 5, 3};
int num = 0, i;
for (i=0; i < 7; i++)
num ^= arr[i];
printf("%i\n", num);
这将打印" 1"，这是唯一出现一次的" 1"。
之所以有效，是因为第一次我们输入数字时，它会用自身标记num变量，而第二次我们会(或者多或者少)不标记num。唯一未标记的是重复项。
回答
顺便说一下，我们可以扩展这个想法，以便在重复列表中很快找到两个唯一的数字。
我们将唯一数字称为a和b。首先，按照凯尔(Kyle)的建议，对所有事物进行XOR。我们得到的是一个^ b。我们知道a ^ b！= 0，因为a！= b。选择a ^ b的任意1位，并将其用作掩码-更详细地：选择x作为2的幂，以使x＆(a ^ b)为非零。
现在将列表分为两个子列表-一个子列表包含y＆x == 0的所有数字y，其余的进入另一个子列表。通过选择x的方式，我们知道a和b在不同的存储桶中。我们还知道，每对重复项仍在同一存储桶中。因此，我们现在可以将旧的" XOR-em-all"技巧分别应用于每个存储桶，并发现a和b完全相同。
am
回答
排序方法和XOR方法具有相同的时间复杂度。如果我们假设两个字符串的按位XOR是恒定时间操作，则XOR方法仅为O(n)。这等效于说数组中整数的大小由一个常数限制。在这种情况下，可以使用基数排序对O(n)中的数组进行排序。
如果数字不受限制，则按位XOR将花费时间O(k)，其中k是位字符串的长度，而XOR方法将需要O(nk)。现在，再次，基数排序将以时间O(nk)对数组进行排序。
回答
如果数据集不遵循规则，则Kyle的解决方案显然不会捕获情况。如果所有数字都是成对出现，则算法将得出零结果，就好像零是唯一出现一次的唯一值一样。
如果有多个单一出现值或者三重出现，结果也将是错误。
测试数据集可能最终会花费更昂贵的算法，无论是在内存还是时间上。
Csmba的解决方案确实显示了一些错误数据(没有或者没有一个以上的出现值)，但没有显示其他数据(四倍)。关于他的解决方案，取决于HT的实现，内存和/或者时间大于O(n)。
如果我们不能确定输入集的正确性，则将整数本身作为哈希键的排序和计数或者使用哈希表计数的出现次数都是可行的。
