佚名通过本文主要向大家介绍了两个数组的交集,求两个数组的交集,php数组取交集,数组求交集,数组取交集等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：如何快速找出两个数组的交集，前提是两个数组都是百万级的
描述:
解决方案1:
描述:
快速找出两个数组的交集，两个数组大小分别是百万级的。
PS ：hash算法
解决方案1:
1.将一个数组存入hashset中,O(N)
2.遍历另一个数组,判断元素是否在set里,O(N)
总算法时间复杂度O(N)
而@windoze 的算法中,排序最快也是O(NlogN),所以,我的会快一些(如果是无序的话)
先确保两个数组都是按相同方向排好序的，剩下的就是个O(N)的算法了。
PS. 题主其实没说清楚，按照定义，只有“集合”才有“交集”，“集合”中不能有重复的元素，但“数组”没这个限制。