我想知道的算法来确定相等的元素（例如，整数）两个数组的交集，而无需使用任何外部数据结构（如哈希表）有效（O（nlogn））？

I would like to know the algorithm to determine the intersection of two arrays of equal elements (say, integer) without using any external data structure (like hash table) efficiently (O(nlogn))?

推荐答案

排序，然后循环使用迭代器每个元素数组：

sort, then iterate using an iterator to each element array:

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）