java - 如何快速找出两个数组的交集，前提是两个数组都是百万级的

Question

快速找出两个数组的交集，两个数组大小分别是百万级的。
PS ：hash算法

Answer 1

先確保兩個陣列都是以相同方向排好序的，剩下的就是個O(N)的演算法了。

PS. 題主其實沒說清楚，按照定義，只有“集合”才有“交集”，“集合”中不能有重複的元素，但“數組”沒這個限制。

Answer 2

1.將一個陣列存入hashset中,O(N)
2.遍歷另一個陣列,判斷元素是否在set裡,O(N)
總演算法時間複雜度O(N)
而@windoze 的演算法中,排序最快也是O(NlogN),所以,我的會快一些(如果是無序的話)

Answer 3

PHP有什麼好辦法實現