比如说,我有10亿个数字存储在一个文件中.我怎么能找到之前曾经出现过的数字？
好吧,我不能只是在数组中一次填充数十亿个数字,然后保持一个简单的嵌套循环来检查数字是否已经出现过.
你会如何解决这个问题？
提前致谢 :)
我曾经把它作为一个面试问题.
这是一个O(N)的算法
使用哈希表.按顺序存储指向数字的指针,其中散列键是根据数值计算的.一旦发生碰撞,您就找到了副本.
下面,@ Phimuemue明确指出,在保证冲突之前,4字节整数具有固定的界限; 即2 ^ 32,或约.4GB.在伴随此答案的对话中考虑时,此算法的最坏情况内存消耗将大大降低.
此外,使用如下所述的位阵列可以将存储器消耗减少到1/8,512mb.在许多机器上,这种计算现在可以不考虑任何持久的散列,或在-高性能少排序优先策略.
现在,较长的数字或双精度数字是位阵列策略的低效方案.
当然需要采取一些"特殊"哈希表:
采用由2 ^ 32位组成的哈希表.由于问题是关于4字节整数,因此它们中至多有2 ^ 32个不同,即每个数字一位.2 ^ 32位= 512mb.
所以现在只需确定hashmap中相应位的位置并进行设置即可.如果遇到已经设置的位,则序列中已经出现了该数字.