算法找到两个集合相交，而无需使用任何数据结构 [英] Algorithm to find intersection of two sets without using any data structure

问题描述

我想知道的算法来确定相等的元素（例如，整数）两个数组的交集，而无需使用任何外部数据结构（如哈希表）有效（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）

这篇关于算法找到两个集合相交，而无需使用任何数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！