计算线性时间的交集？

Question

是否存在一个算法,给定两组,在线性时间内计算它们的交集？

我可以运行两个for循环来检查所有元素对,记录我在两个集合中找到的元素.但是,运行时间将为O(n ²).我如何在O(n)时间内完成此操作？

Answer 1

这取决于您的设置实现.

如果你有一个哈希集(O(1)查找),那么所有其他海报指示的方法是正确的.迭代第一组中的所有元素.如果它在第二组中,则将其添加到结果中.这在O(n)时间内运行.

如果你有一个树集(O(lg n)查找),那么这种方法将起作用,但它在O(n lg n)时间内运行.你可以做得更好; 有一个O(n)解决方案.我假设你有某种迭代器可以按升序遍历两个集合的元素.如果你这样做,那么问题是"按排序顺序给出两个列表,找到它们的交集." 这可以使用您用于合并两个范围的算法的修改版本来完成.我们的想法是跟踪两个迭代器.在每个步骤中,比较范围的第一个元素.如果它们相等,则将元素添加到交集处并向前推进两个迭代器.如果第一个小于第二个,则推进第一个迭代器.如果第一个元素更大,则前进第二个迭代器.这在时间O(n)中运行,因为每次迭代消耗至少一个元素,并且总共只有O(n)个元素.

Answer 2

我想知道没人提到哈希表.
无论你的set实现如何(即使'set'在这里意味着一个简单的数组),你也可以

1. 将第一组的内容放入哈希表和
2. 迭代第二组,检查哈希表是否包含当前元素.

O(n)

Answer 3

对于集合 1 中的所有元素：检查该元素是否在集合 2 中。您可以实现一个具有摊销 O(1) 查找时间的集合。