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