84669 人学习
152542 人学习
20005 人学习
5487 人学习
7821 人学习
359900 人学习
3350 人学习
180660 人学习
48569 人学习
18603 人学习
40936 人学习
1549 人学习
1183 人学习
32909 人学习
快速找出两个数组的交集,两个数组大小分别是百万级的。 PS :hash算法
走同样的路,发现不同的人生
先确保两个数组都是按相同方向排好序的,剩下的就是个O(N)的算法了。
PS. 题主其实没说清楚,按照定义,只有“集合”才有“交集”,“集合”中不能有重复的元素,但“数组”没这个限制。
1.将一个数组存入hashset中,O(N) 2.遍历另一个数组,判断元素是否在set里,O(N) 总算法时间复杂度O(N) 而@windoze 的算法中,排序最快也是O(NlogN),所以,我的会快一些(如果是无序的话)
PHP有什么好办法实现
先确保两个数组都是按相同方向排好序的,剩下的就是个O(N)的算法了。
PS. 题主其实没说清楚,按照定义,只有“集合”才有“交集”,“集合”中不能有重复的元素,但“数组”没这个限制。
1.将一个数组存入hashset中,O(N)
2.遍历另一个数组,判断元素是否在set里,O(N)
总算法时间复杂度O(N)
而@windoze 的算法中,排序最快也是O(NlogN),所以,我的会快一些(如果是无序的话)
PHP有什么好办法实现