84669 personnes étudient
152542 personnes étudient
20005 personnes étudient
5487 personnes étudient
7821 personnes étudient
359900 personnes étudient
3350 personnes étudient
180660 personnes étudient
48569 personnes étudient
18603 personnes étudient
40936 personnes étudient
1549 personnes étudient
1183 personnes étudient
32909 personnes étudient
快速找出两个数组的交集,两个数组大小分别是百万级的。 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有什么好办法实现