计算交集的线性时间？ [英] Computing set intersection in linear time?
问题描述
有没有一种算法，给出了两套，计算它们的交集线性时间？
Is there an algorithm that, given two sets, computes their intersection in linear time?
我可以运行两个为循环检查所有元素对，记录，我觉得在这两个集合的元素。然而，runninng时间将是为O（n 2 ）。如何做到这一点的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(n2). 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屋！
