Ksh*_*jee 9 c++ algorithm
有两个整数数组,每个都在非常大的文件中(每个文件的大小都大于RAM).如何在线性时间内找到数组中的公共元素.
我找不到解决这个问题的合适方案.有任何想法吗？
APr*_*mer 12
对一个文件进行一次传递构建一个位图(如果整数范围对于内存中的位图来说太大,则为Bloom过滤器).
另一个文件中的一个传递找到重复项(或者如果使用Bloom过滤器则为候选项).
如果使用Bloom过滤器,则结果是概率性的.新的通行证可以减少误报(布隆过滤器没有假阴性).
Com*_*Man 6
假设整数大小为4个字节.现在我们可以有最多2 ^ 32个整数,即我可以有一个2 ^ 32位(512 MB)的位向量来表示每个位重复1个整数的所有整数.1.使用全零初始化此向量2.现在浏览一个文件,如果找到整数,则将此向量中的位设置为1.3.现在浏览其他文件并查找位Vector中的任何设置位.
时间复杂度O(n + m)空间复杂度512 MB
归档时间：
14 年，1 月 前
查看次数：
2697 次
最近记录：
9 年，1 月 前