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

Question

我想知道算法确定两个相等元素数组(比如整数)的交集,而不使用任何外部数据结构(如哈希表)(O(nlogn))？

Answer 1

sort,然后使用迭代器迭代到每个元素数组:

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)