求数组的交集intersection

Published: 27 Jun 2016 Category: algorithm

如何快速地求两个数组的交集?

比如A={6,2,4,1},B={2,9,4,3,2},那么A&B={2,4}。

算法1

暴力算法,遍历A和B,算法复杂度为 O(m*n)。

算法2

对A和B进行排序,然后用两个下标进行循环遍历,类似于Merge排序中的遍历方式。 这种算法的复杂度为O(n*lgn)+ O(m+n),即复杂度在排序那部分。

这里有人提出用二叉搜索查找,对于两个都已排序的数组来说,不是很建议使用,因为二叉搜索的复杂度O(n*lgm) 还是会大于下标遍历复杂度O(m+n).

算法3

利用计数排序。这种基于非比较的排序能使算法的复杂度降低为O(n+m)(最后要遍历一遍合并的数组,所以复杂度不是O(k), k为n和m两者中的最大值)。

具体方法,是求出两个数组的最小值和最大值,求出差值,然后声明一个长度为差值的长数组,之后分别遍历A和B,用A或B中的值作为长数组的下标,对长数组中的值进行加1操作(每一次遍历A或B时,长数组的下标出现多次都只加1),最后遍历一遍长数组,输出值为2的下标即可。

算法4

Hash算法。 将长度较短的数组放入Hash表,然后遍历一遍长度较长的数组。该算法复杂度为O(k)。 (对于A和B中的所有元素,都要求一遍Hash。将长度较短的数组放入Hash表的一个原因是降低空间复杂度,另一个原因是避免出现hash碰撞)

扩展

  1. 其中A是已经排好序的,B是乱序的,在这个条件下用什么算法比较好?
    继续用算法2中方法,这时就可以引入二叉搜索查找了。复杂度为O(n*lgm)。

  2. 如果两个数组都很大,任意一个都无法一次性全部加载到内存,这个时候要如何做? (唉,自己给自己出了一道难题)

曾经有次面试被人问到过类似的题目,是说两台机器上存了手机号码,现在要把两台机器上的共有的手机号码抽取出来,同样内存大小有限制,该怎么做?

答案在另一篇博文里面。–>海量数据分析处理的十个方法

参考

最快速度求两个数组之交集算法
海量数据分析处理的十个方法