有几种方法可以使用排序 O(mlog(n)) 或散列 O(m+n) 与额外空间 O(m) 或 O(n) 或 O(m+n) 中的索引增量方法来解决此问题。
但是如果内存有限并且我的数组大小在数百万范围内，我会更感兴趣。
我们可以将数组 A 或 B 分成段并将其加载到内存中，但我想知道是否有更好的方法。
问问题
1833 次
3 回答
2
元素区别问题（至少和你的问题一样难）是不O(nlogn)使用任何额外的空间。
但是，使用在平均情况下实际上可以改进的散列解决方案。
您建议的方法实际上是在数据库系统中实现交集的方法之一：
创建k存储桶（在磁盘上），遍历列表，并将每个元素添加e到bucket[hash(e)].
完成后，假设有足够的空间使每个存储桶足够小以加载到内存1，您只需要bucket[i]为每个列表加载 - 并在每个存储桶的内存交集（基于排序和迭代）中执行。
结果将为您提供交叉点的答案 - 这是常见的元素。
在数据库系统中完成它（交集）的另一种方式是使用外部排序（通常是合并排序的变体）和迭代，或创建针对磁盘优化的索引（例如B+ 树）。
（1）通常是这种情况，如果不是 - 对每个桶（具有不同的哈希函数）重复该过程，直到您有足够小的桶。
于 2012-12-20T06:06:35.607 回答
1
您可以使用外部合并排序在有限 RAM 的情况下进行排序。 http://en.wikipedia.org/wiki/External_sorting
于 2012-12-20T01:34:24.623 回答
1
如果数组已排序，只需同时遍历数组并复制公共元素。在大数组的情况下，加载其中的一部分。
于 2012-12-20T01:31:53.373 回答