算法&大数据--(1)求交集

该系列文章将找一些有趣的算法题目，针对少量数据集和海量数据分别寻找解决方案，也欢迎大家多多指教！

题目：

• 求两个整数数组的交集，如下：
• int[] array1={2,6,3,9,4}
• int[] array2={4,7,9,1}
• array1,array2数组长度分别为N,M
• 交集为：{4,9}

解法：

方法一：暴力法

暴力法是最简单，最粗暴的解法。在这个 硬件成本越来越低，机器配置越来越高，时间成本越来越贵的年代，

很多简单一次性的任务不妨使用暴力算法试一下。笔者一直信奉没有最好的解决方案，只有适合的解决

方案，快速简单解决问题才是王道。

用array1中的每个元素分别于array2中的元素逐个比较。

For item1<-array1
     For item2<-array2
          If item1==item2  Then print item1

总的时间复杂度为O(N*M)

方法二：单排序后比较法

对数据进行排序能够提高检索速度（后续查找可以采用折半查找），尤其是后续需要重复使用这批排序数据时，效果更明显。

Sort array1                                     ---(1)  排序可以实现时间复杂度：O(NlogN)
For item2<-array2
   使用折半查找法查找item2 是否存在array1中          ---(2)  折半查找时间复杂度为：O(logN)
   IF Exists Then print item2

总的时间复杂度为： O(NlogN)+M*O(logN)

此处有一个有趣的话题：是对长度较长的数组进行排序还是对长度较短的数组进行排序时间复杂度更低？欢迎探讨

方法三：双排序后比较法

分别对两个数组进行排序，然后从小到大同时遍历比较两个数组。

Sort array1                  --(1) O(NlogN)
Sort array2                  --(2) O(MlogM)
i,j<-0
While i<N and j<M
    While array1[i] <array2[j] and i<N  Then i++
    While array1[i] >array2[j] and j<M  Then j++
    If i<N and j<M  Then print array1[i]
    i++,j++

总的时间复杂度为：O(NlogN)+O(MlogM)+O(Min(N,M))

方法四：哈希表法

哈希表可以说是实际应用最广泛的一种数据结构，可以在O(1)的时间查找元素，采用哈希表进行数据比较是一种非常有效的手段，

很多大数据问题进行拆分后都可以用哈希表做数据比较。

HashSet set
For item1<-array1
    set<-item1                                            --(1)  构建hash O(1)
For item2<-array2
     If set contains item2 Then print item2     --(2)  hash查找 O(1)

时间复杂度达到O(N+M)

-------------------------The End

转载请注明作者，及原文链接