高效列表交集算法

Question

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

Answer 1

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

Answer 2

在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;

}