有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字

mirnshi

不用说100万个数字了，就是100万个字符串，也是小case，用bloom filter轻松搞定。

mirnshi

回复  mirnshi

网上查到------
    Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某 ...
hq8318 发表于 2011-08-14 22:33

1. 多重哈希可以降低冲突
2. 如果必须是100%，可以在冲突后，再进行循环检索。这个空间和时间要求都能很好的掌控了。

mirnshi

“如果必须是100%，可以在冲突后，再进行循环检索”，这样就不是“小case，用bloom filter轻松搞定”吧。
hq8318 发表于 2011-08-15 14:14

Bloom filter可以极大降低空间时间复杂度。N多人研究过并且可以在网上找到成堆的论文，具体可以参考这些论文。

BTW，Bloom filter不适合题目要求（1到9，重复100万次，其中只有1个数字重复2次）。Bloom filter是针对楼上100万个不同数字提出的。