Question

请教算法：有两个文本文件：f1，f2，一行一个记录，如何快速找出同在f1和f2中的记录？

文件记录格式：为数字，最小为2，最大为700000000（可以理解为7亿，也可以理解为9位数）.
f1包含5千万记录。
f2包含3千万记录。
算法最好只遍历一遍数据。
如果涉及位图之类的方法，请辅以代码（java）解释。
按代码给分。
谢谢。

Answer 1

以下我只叙述一下我所能想到的策略：
1.直接f1中一个记录一个记录的到f2中寻找，复杂度为o（mn）
2.可以将f2进行快速排序之后，再拿f1中一个记录一个记录的到f2中寻找，这个可以用折半查找，复杂度为o（nlgn+mlgn）
3.将f1，f2都进行快排之后，开始用一个i和一个j分别指向f1和f2，这样i和j都可以一直向后移动，不会出现i，j回退的现象，这样的复杂度为o（mlgm+nlgn+？）？表示我不太确定i，j所需要的时间，不过这个肯定相当快速。
4,由于都是数字，可以采用链式基数排序的方法，用十个桶对f1排序，用10个桶对f2进行排序，排序所需要的时间为o（d（m+d+n+d))（d=10），然后再进行3中所叙述的类似的方式，一直向后指
5，对f1构建小顶堆，f2构建小顶堆，时间复杂度为o（m+n),然后拿着堆顶元素对应着比较，删除堆顶这样的操作这个o（mlgm+nlgn)
6,用hash表，n进行散列，m去查找，应该是o（m+n)
我习惯c语言，没有用过java，不知道，我认为java应该都有对应的算法的，它的封装性太好了。
仅仅是个人的一些经验而已

Answer 2

这个题比楼上快的一种算法是哈希表，用VECTOR来实现这个哈希表。
先读入第一个文件里面的五千万个数字，把它们做进哈希表里面，具体怎么hash不用太详细讲把？就是把读入的数字模一个大质数，然后把这个数字存到这个余数开头的那个VECTOR里面。
然后读入第二个文件里面的三千万个数字，之后做一次查询操作就可以了。
均摊的时间复杂度是O(8千万)，也就是只读一遍就可以了

时间复杂度就是读数据的复杂度。
那么请给我分把