algorithm - 在不使用任何数据结构的情况下找到两组交集的算法

Question

我想知道在不使用任何外部数据结构（如哈希表）的情况下有效地确定两个相等元素（比如整数）数组的交集的算法（O（nlogn））？

Answer 1

排序，然后使用迭代器对每个元素数组进行迭代：

if A[iter1] > B[iter2]: increase iter2
else if A[iter1] < B[iter2]: increase iter1
else: element is in intersection, print and increase both iters

排序是O(nlogn)，迭代是O(n)，总O(nlogn)

Answer 2

• 对数组进行排序
• 遍历它们并存储匹配项

就像是...

var A = [0...N];
var B = [0...N];
var result = [];
Array.sort(A);
Array.Sort(B);
for(var x=0, y=0; x < N && y < N; x++) {
    while(A[x] < B[y] && y < N) {
        y++;
    }
    if(A[x] == B[y]) {
        result.push( B[y++] );
    }
}

Answer 3

n 个集合的交集

给定 n 组不同大小的整数。每个集合也可能包含重复项。如何找到所有集合的交集。如果一个元素在所有集合中多次出现，则应该在结果中多次添加它。

例如，考虑有三个集合 {1,2,2,3,4} {2,2,3,5,6} {1,3,2,2,6}。给定集合的交集应该是 {2,2,3}

以下是解决此问题的有效方法。

1. 对所有集合进行排序。
2. 取最小的集合，将所有元素及其频率插入到地图中。
3. 对于地图中的每个元素，请执行以下操作 .....a。如果该元素不存在于任何集合中，请忽略它……..b。查找每个集合中元素的频率（使用二分搜索）。如果它小于地图中的频率，则更新频率……..c。如果在所有集合中都找到该元素，则将其添加到结果中。

时间复杂度：假设有“n”个列表，列表的平均大小为“m”。排序阶段需要 O( n* m *log m) 时间（对 n 个平均长度为 m 的列表进行排序）。搜索阶段需要 O( m * n * log m) 时间。（对于列表中的每个元素，我们用 log m 时间搜索 n 个列表）。所以总的时间复杂度是O(n m log m)。

辅助空间：用于存储地图的 O(m) 空间。