问在存储在文件中的数字中查找再次出现的数字

EN

我曾经在面试中问过这个问题。

这是一个O(N)的算法

使用哈希表。按顺序存储指向数字的指针，其中哈希键是根据数值计算得出的。一旦你有了碰撞，你就找到了你的副本。

作者编辑：

下面，@Phimuemue提出了一个很好的观点，即在保证冲突之前，4字节整数有一个固定的界限；即2^32，或者说大约2^32。4 GB。当在此答案附带的对话中考虑时，此算法的最坏情况下的内存消耗将大大减少。

此外，使用如下所述的位数组可以将内存消耗减少到1/8,512mb。在许多机器上，现在可以在不考虑持久散列或性能较差的排序优先策略的情况下进行这种计算。

现在，对于位数组策略来说，较长的数字或双精度数字是效率较低的方案。

Phimuemue编辑：

当然，我们需要使用一些“特殊的”哈希表：

以一个包含2^32位的哈希表为例。由于问题询问的是4字节整数，因此最多有2^32个不同的整数，即每个数字对应一位。2^32位= 512mb。

因此，现在只需确定相应位在hashmap中的位置并对其进行设置。如果遇到已设置的位，则该数字已出现在序列中。

重要的问题是，你是否想要高效地解决这个问题，或者你是否想要。

如果你真的有100亿个数字，并且只有一个重复，那么你就处于“大海捞针”类型的情况下。直观地说，如果没有非常肮脏和不稳定的解决方案，如果不存储大量的数字，就没有希望解决这个问题。

相反，转向概率解决方案，它已经在这个问题的几乎所有实际应用中使用(在网络分析中，您试图做的是寻找鼠标，即在大型数据集中很少出现的元素)。

一种可能的解决方案，可以找到准确的结果:使用足够高分辨率的Bloom filter。要么使用过滤器来确定元素是否已经被看到，或者，如果你想要完美的准确性，可以使用(正如kbrimington建议的那样使用标准哈希表)过滤器来过滤掉你不可能看到的元素，然后在第二次遍历时，确定你实际看到的元素两次。

如果你的问题稍有不同-例如，你知道你至少有0.001%的元素重复了两次，你想要找出大约有多少，或者你想从这些元素中随机抽样-那么在Flajolet & Martin，Alon等人的脉络中，存在着一大堆概率流算法，它们非常有趣(更不用说效率很高了)。

读取文件一次，创建一个哈希表，存储您遇到每个项目的次数。但是等等！不是使用项目本身作为关键字，而是使用项目本身的散列，例如最低有效位，假设20位(1M个项目)。

在第一次传递之后，计数器大于1的所有项都可能指向重复的项，或者是假阳性。重新扫描文件，只考虑可能导致重复的项(查询表1中的每一项)，现在使用实值作为键构建一个新的哈希表，并再次存储计数。

在第二次遍历之后，第二个表中计数大于1的项目就是您的副本。

这仍然是O(n)，只是比单次通过慢两倍。