在线性时间内计算集合交集? [英] Computing set intersection in linear time?

问题描述

有没有一种算法可以在给定两个集合的情况下，在线性时间内计算它们的交集?

Is there an algorithm that, given two sets, computes their intersection in linear time?

我可以运行两个 for 循环来检查所有元素对，记录我在两个集合中找到的元素.但是，运行时间将为 O(n²).我如何在 O(n) 时间内做到这一点?

I can run two for loops to check all pairs of elements, recording elements that I find in both of the sets. However, the runninng time will be O(n²). How do I do this in O(n) time?

推荐答案

这取决于你的设置实现.

That depends on your set implementation.

如果您有一个哈希集(O(1) 查找)，那么所有其他发布者指出的方法是正确的.遍历第一组中的所有元素.如果它在第二组中，则将其添加到结果中.这在 O(n) 时间内运行.

If you have a hash set (O(1) lookup), then the approach indicated by all the other posters is correct. Iterate across all the elements in the first set. If it's in the second set, then add it to the result. This runs in O(n) time.

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

If you have a tree set (O(lg n) lookup), then this approach will work, but it runs in O(n lg n) time. You can do better; there's an O(n) solution. I assume that you have some sort of iterator that can traverse the elements of the two sets in ascending order. If you do, then the question is "given two lists in sorted order, find their intersection." This can be done using a modified version of the algorithm you use to merge two ranges. The idea is to keep track of the two iterators. At each step, compare the first elements of the ranges. If they're equal, add the element to the intersection and advance both iterators forward. If the first is less than the second, then advance the first iterator. If the first element is greater, then advance the second iterator. This runs in time O(n) because each iteration consumes at least one element, and there's only O(n) elements in total.

这篇关于在线性时间内计算集合交集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！