1回答

liuyubobobo

2018-07-28

已采纳

要想看follow up 3，需要先理解一下follow up 2：）

在这个题目中，给的测试用例看起来nums1比nums2多，或者nums1和nums2的长度在同一个数量级。在这种情况下，我们将nums2的内容扔进哈希表，扫描nums1和哈希表作比对得到答案，是没有问题的。

但是，其实，nums1和nums2的地位是对等的。换句话说，让nums1是nums2，nums2是nums1，得到的结果是一样的。在这种情况下，使用nums1还是nums2来建立哈希表都是ok的。所以，在follow up 2中，说如果nums1比nums2的长度小的话，使用nums1建立哈希表，转而扫描num2去和哈希表比对，更优。时间复杂度没变，空间复杂度降低。

同理，在follow up 3中，只强调了nums2是内存无法装载的。那么如果nums1可以放在内存中的话，就可以把nums1做成哈希表，然后从磁盘中逐步读取nums2的内容（扫描一个文件内容不需要把整个文件中的数据全都读入内存），和哈希表作比对即可。

真正困难的是：如果nums1和nums2都无法载入内存怎么办？此时，follow up 1突然有用了。因为对于follow up 1来说，使用Two Pointers的思想，根本不需要哈希表！（这个过程，可以使类比归并排序的归并过程，很像。更多Two Pointers思想例题，可以参考我的课程《玩转算法面试》，或者扫一遍Leetcode中有Two Pointers标签的问题。传送门：https://leetcode.com/tag/two-pointers/）。

所以，此时可以使用外存排序算法（抱歉，我的所有课程都不包含外存排序算法，可以搜索“外部排序”或者相应的英文“External Sorting”进行学习），先将nums1和nums2在外存中整理成有序的。之后，使用Two Pointers的思想来解决：）

最后，其实大量的“大规模数据”的算法问题，都涉及缓存，分治，分块儿处理等思想。其实可以简单理解成：每次只能把一部分数据读进来，怎么办。网上有一些很好的总结（好吧，不一定很好，但是自己深入研究，够用了），如果对这类问题感兴趣，可以自行搜索研究学习一下。比如这个：https://blog.csdn.net/v_JULY_v/article/details/6279498

我的所有课程暂时都只涉及内存算法。有机会我会考虑针对“大规模数据”，牵扯外存算法的问题，再出课向大家介绍一下的：）

加油！

2

1

儿歌逍遥

非常感谢！感谢波波老师给我提供的思路

2018-07-30

共1条回复