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

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:

fender0107401

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

fender0107401

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

全都是int的整数。

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

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

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

fender0107401

__BlueGuy__ 发表于 2013-04-01 14:38
楼主不适合写程序， 鉴定完毕 ！

装逼男。

别动不动的就在那里“笑而不语”，我相信众多版友都知道你装逼装到没话说的时候经常整一句“笑而不语”。

fender0107401

__BlueGuy__ 发表于 2013-04-01 16:26
排序 + 二分 比你的算法不高明？ 我哪里装了？
查个数连个 二分都想不到， 你写JB个程序啊 ...

果然又笑而不语了。。。

用这种方式装逼的还真是少见，基本上算得是硬装逼流了。

注：别以为二分查询很牛逼，二分查询的计算复杂性是O(1)，但是这并不代表你说的那个方法跑的快，以你这种经常“笑而不语”的智商，我相信你肯定能理解。

fender0107401

__BlueGuy__ 发表于 2013-04-01 16:49
还有，你都不知道引入 计算复杂度 的目的是什么？
计算复杂度低， 程序能不快吗 ， 还不一定， 不一定你妹 ...

你真以为O(1)就快吗？

那你这水平就不用谈了。

你还是在自己找个地方笑而不语去吧。

fender0107401

不是2个数组是M个数组。 :wink:

fender0107401

__BlueGuy__ 发表于 2013-04-01 21:51
你找个O（1）不快的例子我看看

你要是保证以后在CU上不骂人，我就给你举个例子出来。