关于算法：在列表中查找单个数字

找到在列表中只出现一次的数字的最佳算法是什么，其中所有其他数字恰好发生两次。

因此，在整数列表中(让它作为一个数组)，每个整数重复两次，除了一个。 找到那个，什么是最好的算法。

最快(O(n))和最大内存效率(O(1))方式是XOR操作。

在C：

这会打印"1"，这是唯一一次出现的。

这是有效的，因为第一次敲击数字时，它会自动标记num变量，第二次将num自身标记为自身(或多或少)。唯一没有标记的是您的非重复。

顺便说一句，您可以扩展这个想法，以便在重复列表中快速找到两个唯一的数字。

我们称之为唯一数字a和b。首先考虑一切的异或，正如凯尔建议的那样。我们得到的是^ b。我们知道a ^ b！= 0，因为a！= b。选择任何1位a ^ b，并将其用作掩码 - 更详细：选择x作为2的幂，使x＆(a ^ b)非零。

现在将列表拆分为两个子列表 - 一个子列表包含y和x == 0的所有数字y，其余子列表位于另一个子列表中。顺便说一下，我们选择x，我们知道a和b在不同的桶中。我们也知道每对副本仍然在同一个桶中。因此，我们现在可以独立地将"XOR-em-all"技巧应用于每个桶，并发现a和b完全是什么。

巴姆。

O(N)时间，O(N)记忆

HT =哈希表

HT.clear()
按顺序查看列表
对于您看到的每个项目

最后，HT中的项目是您要查找的项目。

注意(credit @Jared Updike)：此系统将查找所有项目的奇数实例。

评论：我不知道人们如何投票给你提供NLogN性能的解决方案。宇宙是哪个"更好"？
我更加震惊你标记了NLogN解决方案的接受答案...

我同意，如果要求内存保持不变，那么NLogN将是(到目前为止)最佳解决方案。

如果数据集不符合规则，Kyle的解决方案显然不会遇到问题。如果所有数字都成对，则算法将得到零的结果，完全相同的值，就好像零将是唯一出现单一值的值。

如果存在多个单个出现值或三元组，则结果也将是错误的。

测试数据集可能会在内存或时间上以更昂贵的算法结束。

Csmba的解决方案确实显示了一些错误数据(没有或多于一个出现值)，但没有显示其他(四元组)。关于他的解决方案，取决于HT的实现，存储器和/或时间多于O(n)。

如果我们无法确定输入集的正确性，排序和计数或使用哈希表计数出现，整数本身就是哈希键，这两者都是可行的。

在Ruby中实现：

我会说使用排序算法然后通过排序列表来查找数字是一个很好的方法。

现在问题是找到"最好的"排序算法。有很多排序算法，每个都有它的优点和缺点，所以这是一个非常复杂的问题。维基百科条目似乎是一个很好的信息来源。

排序方法和XOR方法具有相同的时间复杂度。如果您假设两个字符串的按位XOR是恒定时间操作，则XOR方法仅为O(n)。这相当于说数组中整数的大小由常量限定。在这种情况下，您可以使用Radix排序在O(n)中对数组进行排序。

如果数字不受限制，则按位XOR需要时间O(k)，其中k是位串的长度，并且XOR方法取O(nk)。现在，Radix sort将在时间O(nk)中对数组进行排序。

取决于数字的大小/多样性。可以应用基数排序，这将在很大程度上减少O(N log N)解的排序时间。

似乎你可以做的最好的事情就是遍历列表，因为每个项目都将它添加到"看到"项目列表中，或者如果它已经存在则将其从"看到"中删除，最后列出"看到""项目将包括单数元素。这是关于时间的O(n)和关于空间的n(在最坏的情况下，如果列表被排序则会好得多)。

它们是整数的事实并没有真正考虑因素，因为添加它们没有什么特别之处......是吗？

题

我不明白为什么选择的答案是任何标准的"最佳"。 O(N * lgN)> O(N)，它改变了列表(或者创建了它的副本，它在空间和时间上仍然更加昂贵)。我错过了什么吗？

你需要用"最好"来指定你的意思 - 对某些人而言，速度是最重要的，并且将答案限定为"最佳" - 对于其他人来说，如果解决方案更具可读性，他们可能会原谅几百毫秒。

除非你更具体，否则"最好"是主观的。

那说：

遍历数字，对于每个数字搜索该数字的列表，当您达到只返回1作为搜索结果数量的数字时，您就完成了。

您可以简单地将集合中的元素放入哈希值，直到找到冲突为止。在红宝石中，这是一个单行。

所以，find_dupe([1,2,3,4,5,1])将返回1。

这实际上是一个常见的"技巧"面试问题。它通常是一个带有一个重复的连续整数列表。在这种情况下，面试官经常会寻找你使用n整数技巧的高斯和，例如n*(n+1)/2从实际总和中减去。教科书的答案是这样的。