高效的列表交集算法

Question

高效的列表交集算法

71 algorithm list set-intersection

给定两个列表(不一定排序),找到这些列表的交集的最有效的非递归算法是什么？

Answer 1

Fra*_*ank 36

您可以将第一个列表的所有元素放入哈希集中.然后,迭代第二个,并为其每个元素检查哈希,看它是否存在于第一个列表中.如果是,则将其输出为交集的元素.

然后,可能:*sort list1(time:n log n)*sort list2(time:n log n)*合并两个并检查相同的条目,同时迭代两个排序列表(线性时间) (4认同)
如果您可以访问数组,那么您肯定可以构建自己的哈希表.构建合理的哈希函数通常非常简单. (3认同)
我没有足够的观点来评论其他线程,但关于快速排序是递归的这一点:你可以在没有递归的情况下实现它.请参阅此处,例如:http://www.codeguru.com/forum/archive/index.php/t-333288.html (2认同)

Answer 2

Ane*_*apu 22

您可能想看一下Bloom过滤器.它们是位向量,它给出概率回答元素是否是集合的成员.可以使用简单的按位AND运算来实现集合交集.如果您有大量的空交叉点,Bloom过滤器可以帮助您快速消除这些交叉点.但是,您仍然必须使用此处提到的其他算法来计算实际交点. http://en.wikipedia.org/wiki/Bloom_filter

Answer 3

Tom*_*ter 9

没有散列,我想你有两个选择:

天真的方式是将每个元素与每个其他元素进行比较.为O(n ^ 2)
另一种方法是首先对列表进行排序,然后迭代它们:O(n lg n)*2 + 2*O(n)

只需注意"O(n lg n)*2 + O(n)*2"与"O(n lg n)"相同. (3认同)

Answer 4

zvr*_*rba 7

From the eviews features list it seems that it supports complex merges and joins (if this is 'join' as in DB terminology, it will compute an intersection). Now dig through your documentation :-)

Additionally, eviews has their own user forum - why not ask there_

Answer 5

小智 6

在C++中,可以使用STL map尝试以下内容

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

Run Code Online (Sandbox Code Playgroud)

Answer 6

小智 6

使用set 1构建一个二进制搜索树,O(log n)并使用和迭代set2并搜索BST m X O(log n)总数O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

对于二叉搜索树部分,仍然需要对其中一个列表进行排序(这将为复杂度添加O(m log m)或O(n log n)).这仍然是一个非常有用的答案:在我的情况下,我有两个包含相同对象的列表,但每个列表根据不同的对象属性进行排序 - 我需要获取两个列表中的哪些对象.此答案与每个列表的排序属性无关.谢谢! (2认同)
实际上,构建树是O(n log n)所以它总体上是O((n + m)log n) (2认同)

归档时间：	16 年，7 月前
查看次数：	72537 次
最近记录：	9 年，2 月前