有什么算法可以很快地取到交集。

fender0107401

1. 
   
2. a = {1, 2, 3, 4, 5, 6, 7};
   
3. b = {2, 3, 5};
   

复制代码

如何知道a和b的交集？

数据量可能比较大，所以需要一个快一点的算法。

原始问题在这里：http://bbs.chinaunix.net/thread-4074355-1-1.html

fender0107401

如果总共有M个数组的长度分别是：N_1 N_2 .... N_max。

那我使用quick sort先排序的话，那么每次的排序算法的计算复杂性是O(nlog(n))，所有排序的复杂性加起来是M*O(N_max*log(N_max))。

然后把所有数组连成一个，再次排序那么复杂性是：(M*N_max)*log(M*N_max)，

然后我要对整个数组进行遍历，找出连续重复出现次数等于M的元素，这个复杂性是M*N_max。

所以整个的复杂性是M*N_max + (M*N_max)*log(M*N_max) + M*O(N_max*log(N_max)) = M*(N_max + N_max*log(M*N_max) + O(N_max*log(N_max)))。

这样应该是最快了吧？

fender0107401

:wink:

hellioncu

合并应该可以省去

cokeboL

比如都是int数组
计数：
分配个大数组清零，每个int数组元素作为大数组下标对大数组元素做++，各个数组都弄完之后，遍历一次大数组看哪些元素值和数组个数相等，取其下标为交集

如果是字符串之类的并且字符串数量不是特别大，弄个字符串和int的映射表，一样可以用上面的方法
数量巨大弄映射伤不起的话，楼主描述下数据特点吧，然后再想牛逼的算法吧。。。

fender0107401

hellioncu 发表于 2013-04-01 08:58
合并应该可以省去

fender0107401

cokeboL 发表于 2013-04-01 09:26
比如都是int数组
计数：
分配个大数组清零，每个int数组元素作为大数组下标对大数组元素做++，各个数组都 ...

全都是int的整数。

但是数字范围可能很大，都是数据库里面的主键。

我也想过弄个大点的数组，然后往里面填数据，但是实际中集合里面的整数可能“千”或者“万”为单位的，声明一个大的数组可能需要消耗很多没必要的存储空间。

除非是先映射一下，但是这样似乎比较麻烦。

cokeboL

如果遍历的话，各数组长度分别是 N_MIN， N_1， N_2 。。。 N_MAX

1.先N_MIN和N_1中找，N_MIN中每个元素和N_1中比较看是否有相等的，复杂度为O(N_MIN * N_1)
2.结果再和N_2比较，1中交集个数<= N_MIN，这里复杂度为O(N_MIN * N_2)
。。。
总复杂度为O(N_MIN * （N_1 + N_2 + ... N_MAX))也很大

我去搜搜

selfrun

回复 2# fender0107401


    c++的话用map;  c的话用红黑树做关联数组,标签id做key， value就是标签次数。
往map里或者红黑树里扔一遍，key存在就把value+1。
时间复杂度=sum(N_1....N_max) * log(sum(N_1...N_max);
空间复杂度=标签数。
遍历一遍关联数组，遇到value是M的就取出来。

shan_ghost

先分别排序，设需要求交集的集合共M个，则这样做的复杂度是M*O(N logN);这比先合并后排序的O(M*N log(M*N))要好一些。


分别排序完成后，再以定制的、类归并排序算法处理M个集合的交集。方法是：
0、假设按升序排序
1、从任意集合A开始，找到其他集合中不大于A首元素的元素（前面的全部丢弃）
2、检查所有这些元素是否相同
2.1、都相同，则把这个元素放入交集
2.1.2、从集合A的下一个元素开始，跳到1继续执行
2.2、不相同，以这些元素中最大的一个为准，以该元素所在集合为A，跳到1继续执行


上面这个算法的复杂度大概是O(M*N)。

最终，总体复杂度大约是O(M*N)+M*O(N logN)，即： O(M*N logN)