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

linux_c_py_php

总结一下：

1, 2个数组都排序, 然后求merge.
2, 对数组1建哈希表, 遍历数组2查哈希表.

第二种方法冲突随着规模增大迅速升高, 不过如果支持rehash的哈希表可能会强点.

folklore

回复 41# linux_c_py_php


    支持不支持rehash对本题无影响的
个人支持Hash为比较好的方案。 因为Hash就算只利用了1%的Key空间， 在大规模下也只是匹配100次而已， 这个数目不算大。
当然，前提是Key空间要能自适应目标的规模的大小 。

starwing83

judy array？

fender0107401

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

fender0107401

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

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

insnowind

回复 1# fender0107401

为啥不使用位数组呢，假设你有100万个数，定义一个100万位数组也才需要空间123KB，位数组初始化为0.
然后遍历第一个数组，将对应的元素位置1，然后遍历第二个数组，查看对应的位是否为1即可。

复杂度就是M + N。


   

insnowind

回复 46# insnowind

上面是两个数组的情况，N个数组也是一样，把前两个交集的结果作为一个数组，与后面的持续遍历即可；


   

linux_c_py_php

位图是高效, 面试经常问.

cokeboL

回复 46# insnowind


    如果数组里最大的数字式1 0000 0000呢

shan_ghost

cokeboL 发表于 2013-04-02 11:07

+1024

32位机器上，max_int=2,147,483,647
比你这个数字狠太多了……


PS：位图的确高效。但能用位图的前提是：目标数字本身取值范围较窄。