高效列表交集算法

Question

给定两个列表（不一定排序），找到那些列表的交集的最有效的非递归算法是什么？

Answer 1

您可以将第一个列表的所有元素放入哈希集中。然后，迭代第二个，并针对其每个元素，检查哈希以查看其是否存在于第一个列表中。如果是这样，请将其输出为相交的元素。

Answer 2

在C ++中，可以使用STL映射尝试以下方法vector<int> set_intersection(vector<int> s1, vector<int> s2){&nbsp; &nbsp; vector<int> ret;&nbsp; &nbsp; map<int, bool> store;&nbsp; &nbsp; for(int i=0; i < s1.size(); i++){&nbsp; &nbsp; &nbsp; &nbsp; store[s1[i]] = true;&nbsp; &nbsp; }&nbsp; &nbsp; for(int i=0; i < s2.size(); i++){&nbsp; &nbsp; &nbsp; &nbsp; if(store[s2[i]] == true) ret.push_back(s2[i]);&nbsp; &nbsp; }&nbsp; &nbsp; return ret;}