BYR Achieve · 镜像论坛

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

2017/3/12镜像同步3 回复

大家好，我是时海（欢迎加我的QQ交流：282893304），熟悉java后台开发、大数据开发，该系列文章将找一些有趣的算法题目，针对少量数据集和海量数据分别寻找解决方案，也欢迎大家多多指教！题目：求两个整数数组的交集，如下： 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)

订阅后，新回复会通过你的通知中心匿名送达。