数组合并及升级问题之算法解题思路——每日思考（1）

算法

两个有序数组，合并成一个，刷刷几下写出来了

升级：k个又N个数字的有序数组，合并成一个，刚开始说两两merge，叫在优化一下：后面开始提示我指针的思路，后面回答使用多路指针，找个数组保存一下，本来打算只有思路说服对方，可惜还是要写代码，磕磕碰碰写出来了。再次升级：两个大文件A、B，10亿数据，找出这两个文件中都存在的url，注意内存只有4G；使用hash桶的方式进行

https://www.nowcoder.com/discuss/513761474230153216?sourceSSR=search

2.思考过程 （1）首先我们最常想到的方法是读取文件a，建立哈希表（为什么要建立hash表？因为方便后面的查找），然后再读取文件b，遍历文件b中每个url，对于每个遍历，我们都执行查找hash表的操作，若hash表中搜索到了，则说明两文件共有，存入一个集合。

（2）但上述方法有一个明显问题，加载一个文件的数据需要50亿*64bytes = 320G远远大于4G内存，何况我们还需要分配哈希表数据结构所使用的空间，所以不可能一次性把文件中所有数据构建一个整体的hash表。

（3）针对上述问题，我们分治算法的思想。

step1：遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,...,a999，每个小文件约300M)，为什么是1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把320G大小分为1000份，每份大约300M（当然，到底能不能分布尽量均匀，得看hash函数的设计）

step2：遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,...,b999)（为什么要这样做? 文件a的hash映射和文件b的hash映射函数要保持一致，这样的话相同的url就会保存在对应的小文件中，比如，如果a中有一个url记录data1被hash到了a99文件中，那么如果b中也有相同url，则一定被hash到了b99中）

所以现在问题转换成了：找出1000对小文件中每一对相同的url（不对应的小文件不可能有相同的url）

step3：因为每个hash大约300M，所以我们再可以采用（1）中的想法