高效的列表交集algorithm
给定两个列表（不一定sorting），find这些列表的交集最有效的非recursionalgorithm是什么？
你可以把第一个列表的所有元素放入一个哈希集合。 然后，迭代第二个，并为其每个元素，检查散列，看看它是否存在于第一个列表。 如果是这样，输出它作为交集的一个元素。
你可能想看看布卢姆filter。 它们是位向量，给出一个概率的答案，即一个元素是否是一个集合的成员。 设置十字路口可以用一个简单的按位“与”运算来实现。 如果您有大量空交点，布隆filter可以帮助您快速消除这些交点。 但是，您仍然需要使用这里提到的其他algorithm之一来计算实际交叉点。 http://en.wikipedia.org/wiki/Bloom_filter
没有散列，我想你有两个select：
- 天真的方法是将每个元素与其他元素进行比较。 为O（n ^ 2）
- 另一种方法是先对列表进行sorting，然后迭代它们：O（n lg n）* 2 + 2 * O（n）
从eviewsfunction列表看起来，它支持复杂的合并和连接（如果这是“连接”，如数据库术语，它将计算交集）。 现在挖掘你的文档:-)
此外，eviews有自己的用户论坛 – 为什么不问呢？
（集合1）与O(log n)构build一个二叉查找树并且迭代集合2并且searchBST m XO(log n)所以总O(log n) + O(m)+O(log n) ==> O(log n)(m+1)
在C ++中，可以使用STL映射尝试以下内容
vector<int> set_intersection(vector<int> s1, vector<int> s2){ vector<int> ret; map<int, bool> store; for(int i=0; i < s1.size(); i++){ store[s1[i]] = true; } for(int i=0; i < s2.size(); i++){ if(store[s2[i]] == true) ret.push_back(s2[i]); } return ret; }
这里是另一个可能的解决scheme，它将O（nlogn）的时间复杂度和没有任何额外的存储。 你可以在这里查看https://gist.github.com/4455373
下面是它是如何工作的：假设这些集合不包含任何重复，将所有集合合并为一个并对其进行sorting。 然后循环遍历合并集合，并在每次迭代中创build当前索引i和i + n之间的子集，其中n是宇宙中可用集合的数量。 我们在循环中寻找的是大小为n的重复序列，其数量等于宇宙中的集合数量。
如果i中的子集等于n中的子集，则意味着i处的元素重复n次，这等于集合的总数。 而且由于在任何集合中都没有重复，这意味着每个集合都包含该值，因此我们将其添加到交集。 然后，我们通过i +将索引转移到n和n之间，因为这些索引肯定不会形成重复序列。
首先，使用quicksort对这两个列表进行sorting：O（n * log（n）。然后，通过首先浏览最低值并添加通用值来比较列表。例如，在lua中）：
function findIntersection(l1, l2) i, j = 1,1 intersect = {} while i < #l1 and j < #l2 do if l1[i] == l2[i] then i, j = i + 1, j + 1 table.insert(intersect, l1[i]) else if l1[i] > l2[j] then l1, l2 = l2, l1 i, j = j, i else i = i + 1 end end return intersect end
它是O(max(n, m)) ，其中n和m是列表的大小。
编辑：quicksortrecursion，如在评论中所说，但它看起来像有非recursion 实现
为什么不实现你自己的简单哈希表或哈希集？ 如果你的名单很大，那么避免nlogn相交是值得的。
既然你事先知道了一些关于你的数据，你应该能够select一个好的散列函数。
我第二个“套”的想法。 在JavaScript中，可以使用第一个列表来填充对象，并使用列表元素作为名称。 然后使用第二个列表中的列表元素，看看是否存在这些属性。
如果支持集合 （正如你在标题中所称的那样），通常会有一个交集方法。
无论如何，正如有人说你可以很容易地做到这一点（我不会张贴代码，有人已经这样做），如果你有清单sorting。 如果你不能使用recursion，没有问题。 有快速sortingrecursion实现。
我从中得到了一些很好的答案，你可以申请。 我还没有机会尝试它们，但是由于它们也包含交叉点，因此您可能会发现它们很有用。
在PHP中，类似
function intersect($X) { // X is an array of arrays; returns intersection of all the arrays $counts = Array(); $result = Array(); foreach ($X AS $x) { foreach ($x AS $y) { $counts[$y]++; } } foreach ($counts AS $x => $count) { if ($count == count($X)) { $result[] = $x; } } return $result; }
从Big-Oh表示法的定义：
如果存在正常数c和n 0使得当N≥n0时T（N）≤fc（N），则T（N）= O（f（N））。
实际上，这意味着如果两个列表的大小相对较小，那么每两个for循环中less于100个元素就可以工作。 循环第一个列表，并在第二个寻找类似的对象。 在我的情况下，它工作得很好，因为我的列表中不会超过10 – 20个最大元素。 然而，一个好的解决办法是先sorting第一个O（n log n），再sorting第二个O（n log n）并合并它们，另一个O（n log n）粗略地O（3 n log n），说这两个列表是相同的大小。
使用跳转指针和SSE指令可以提高列表交集效率。
