具体来说，给定两个具有 64 位整数的大文件生成一个包含两个文件中都存在的整数的文件，并估计您的算法的时间复杂度。
你会如何解决这个问题？
最佳答案
我改变主意了；我实际上喜欢@Ryan 的基数排序想法，除了我会针对这个特定问题对其进行一些调整。
让我们假设有太多的数字，以至于它们不适合内存，但我们有我们想要的所有磁盘。 (考虑到问题的措辞，这并非不合理。)
调用输入文件A和B。
因此，创建 512 个新文件；将它们称为文件 A_0 到 A_255 和 B_0 到 B_255。文件A_0获取文件A中高字节为0的所有数字。文件A_1获取文件A中高字节为1的所有数字。文件B_37获取文件B中高字节为37的所有数字。依此类推.
现在所有可能的重复项都在 (A_0, B_0)、(A_1, B_1) 等中，并且可以独立分析这些对(如果需要，还可以递归分析)。并且所有磁盘访问都是相当线性的，这应该是相当有效的。 (如果不是，请调整您用于存储桶的位数...)
这仍然是 O(n log n)，但不需要随时将所有内容保存在内存中。 (在这里，基数排序中的常数因子是 log(2^64) 左右，所以它不是真正的线性，除非你有一个很多超过 2^64 个数字。即使是最大的也不太可能磁盘。)
[编辑，详述]
这种方法的重点是您实际上不必对两个列表进行排序。也就是说，使用此算法，您实际上无法按顺序枚举任一列表的元素。
获得文件 A_0、B_0、A_1、B_1、...、A_255、B_255 后，您只需观察到 A_0 中的任何数字都不能与 B_1、B_2、...、B_255 中的任何数字相同。因此，您从 A_0 和 B_0 开始，找到这些文件共有的编号，将它们附加到输出，然后删除 A_0 和 B_0。然后对 A_1 和 B_1、A_2 和 B_2 等执行相同的操作。
要找到 A_0 和 B_0 之间的公共(public)数字，您只需递归...创建文件 A_0_0，其中包含 A_0 的所有元素，第二 字节为零。创建文件 A_0_1，其中包含 A_0 的所有元素，第二个字节等于 1。依此类推。一旦 A_0 和 B_0 的所有元素都被存储到 A_0_0 到 A_0_255 和 B_0_0 到 B_0_255 中，您可以删除 A_0 和 B_0 本身，因为您不再需要它们。
然后你在 A_0_0 和 B_0_0 上递归以找到共同的元素，一旦它们被分桶就删除它们......等等。
当您最终找到只有一个元素(可能重复)的桶时，您可以立即决定是否将该元素附加到输出文件。
此算法消耗的空间绝不会超过保存这两个文件所需的原始空间的 2+epsilon 倍，其中 epsilon 小于 0.5%。 (证明留给读者作为练习。)
老实说，如果文件太大而无法放入内存，我相信这是所有这些答案中最有效的算法。 (作为一个简单的优化，如果“桶”变得足够小，您可以回退到 std::set 解决方案。)
关于algorithm - 生成一个文件，该文件具有两个包含整数的大文件共有的整数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6520954/