P176. 两个数组的交集

https://algocasts.io/episodes/Yopkg0p3

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
LeetCode进阶提问: * 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
怎么回答呢?

@zhizx

所有因为内存不足,无法一次性把数据加载到内存中的问题,在不允许增加机器(增加内存)的情况下,都是一个解决方案,就是每次读取一部分数据(内存放得下的大小)进行处理,然后分多次读取数据,进行多次处理。(当然,有可能需要对数据进行一些额外处理,但整体思路都是把大块数据分成小块进行处理。

具体到这个问题,由于无法一次性把 nums2 中的所有元素加载到内存,因此一次读取 nums2 的部分数据到内存处理即可。nums1 已经在内存中,像第一种方法那样,构建一个哈希表,存储 nums1 中的元素以及它们的数量。每次处理 nums2 的一部分,把结果保存起来即可。

进一步地,如果 nums1 和 nums2 都无法放入内存,那在内存中构建哈希表的方案可能就不可行了。这时可以用第二种方法(排序版本)。不同的是,这一次由于数据太大,我们要在磁盘上做外排序,排序后的结果同样保存在磁盘中(比如文本文件中)。然后根据给的内存大小,一次性去读一部分的 sortedNums1 和一部分的 sortedNums2,用两个游标来找交集元素。

再进一步地,万一连它们的交集都太大,无法放在内存中。那就当交集达到一个阈值,就把这部分的交集写回磁盘,然后继续查找交集元素。

总结一下,如果数据太大无法完全放入内存,在不能增加机器(增加内存)的情况下,就是分块读入数据进行处理,可能也要分块写出结果数据。这过程中,加上一些必要的数据处理(比如排序,比如聚合统计,这些处理后的数据同样存储在磁盘上)。

P.S. 如果允许增加机器,那就可以考虑把数据分布到不同的机器上进行处理。