在列表中find单个号码
什么是最好的algorithmfind一个数字只发生一次在一个列表中，其中所有其他数字发生了两次。
所以，在整数列表（让我们把它作为一个数组）每个整数重复两次，除了一个。 要find那个，最好的algorithm是什么。
最快的（O（n））和最有效的内存（O（1））方式是异或操作。
在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”，这是唯一一次出现的。
这是有效的，因为你第一次碰到一个数字时，它将自己标记为numvariables，而第二次它将自己标记为num（或多或less）。 唯一没有标记的是你的不重复。
顺便说一句，您可以扩展这个想法，以便在重复列表中快速find两个唯一的号码。
我们称之为独特的数字a和b。 首先采取一切的异或，凯尔build议。 我们得到的是a ^ b。 我们知道a ^ b！= 0，因为a！= b。 selecta ^ b中的任何1位，并将其用作掩码 – 更详细地说：selectx作为2的幂，使x＆（a ^ b）非零。
现在将列表分成两个子列表 – 一个子列表包含y和x == 0的所有数字y，剩下的列在另一个子列表中。 顺便说一下，我们selectx，我们知道a和b在不同的桶中。 我们也知道每一副副本都在同一个桶里。 所以我们现在可以单独应用“XOR-em-all”技巧到每个桶，并且发现a和b是完全的。
巴姆。
O（N）时间，O（N）内存
HT =哈希表
HT.clear（）遍历列表为了您看到的每个项目
if(HT.Contains(item)) -> HT.Remove(item) else ht.add(item)
最后，HT中的物品就是你正在寻找的物品。
注意（credit @Jared Updike）：这个系统会查找所有Odd项目的实例。
评论 ：我不明白人们如何投票给你NLogN性能的解决scheme。 哪个宇宙是“更好”？ 我更震惊的是你标记了接受的答案是NLogN解决scheme…
但是我同意，如果内存需要保持不变，那么NLogN将是（迄今为止）最好的解决scheme。
凯尔的解决scheme显然不能捕捉到数据集不符合规则的情况。 如果所有数字都是成对的，那么algorithm会给出零的结果，如果零是唯一出现的唯一值，则完全相同的值。
如果有多个单独的发生值或三倍，则结果也是错误的。
对数据集进行testing可能最终会导致成本更高的algorithm，无论是在内存中还是在时间上。
Csmba的解决scheme确实显示了一些errouness数据（没有或多于一个单一的发生值），但没有显示其他（四元组）。 关于他的解决scheme，根据HT的实现，内存和/或时间多于O（n）。
如果我们不能确定input集的正确性，那么sorting和计数，或者使用散列表计数发生，而整数本身就是散列键，这两者都是可行的。
我会说，使用sortingalgorithm，然后通过sorting列表find号码是一个很好的方法来做到这一点。
现在问题是find“最好的”sortingalgorithm。 有很多sortingalgorithm，每个algorithm都有其强弱点，所以这是一个相当复杂的问题。 维基百科条目似乎是一个很好的信息来源。
在Ruby中的实现：
a = [1,2,3,4,123,1,2,.........] t = a.length-1 for i in 0..t s = a.index(a[i])+1 b = a[s..t] w = b.include?a[i] if w == false puts a[i] end end
你需要指定“最好”的意思 – 对某些人来说，速度就是最重要的，并且将答案限定为“最好的” – 对于其他人来说，如果解决scheme更具可读性，他们可能会原谅几百毫秒。
“最好”是主观的，除非你更具体。
那就是说：
遍历数字，每个数字search该数字的列表，当您达到search结果数量仅返回1的数字时，您就完成了。
似乎最好的办法是遍历列表，每个项目都将其添加到“已看到”项目列表中，或者如果它已经存在，则将其从“已看到”项目中移除，最后在列表中显示“已看到“项目将包括单数元素。 这是关于时间的O（n）和关于空间的关于n（在最坏的情况下，如果列表被sorting，将会好得多）。
事实上，他们是整数并不是真正的因素，因为没有什么特别的事情可以添加它们来做…在那里？
题
我不明白为什么select的答案是任何标准“最好的”。 O（N * lgN）> O（N），并且它改变列表（或者创build它的副本，这在空间和时间上仍然更昂贵）。 我错过了什么吗？
取决于数量有多大/多小。 基数sorting可能是适用的，这将大大减lessO（N log N）解决scheme的sorting时间。
sorting方法和XOR方法具有相同的时间复杂度。 如果您假定两个string按位“异或”是一个常量时间操作，则XOR方法仅为O（n）。 这相当于说数组中整数的大小是以一个常数为界。 在这种情况下，您可以使用基数sorting来sortingO（n）中的数组。
如果数字不是有界的，则按位XOR需要时间O（k），其中k是位串的长度，XOR方法取O（nk）。 现在基数sorting将在时间O（nk）sorting数组。
你可以简单地把集合中的元素放到哈希中，直到find一个碰撞。 ruby，这是一个单线。
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- integers技巧的高斯和，例如从实际总和中减去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
