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

Question

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

Answer 1

First make sure that both arrays are sorted in the same direction, and the rest is an O(N) algorithm.

PS. The questioner didn't actually make it clear. According to the definition, only "sets" can have "intersections", and "sets" cannot have duplicate elements, but "arrays" do not have this restriction.

Answer 2

1. Store an array in hashset, O(N)
2. Traverse another array to determine whether the element is in the set, O(N)
The total algorithm time complexity is O(N)
In @windoze's algorithm, the fastest sorting is O(NlogN), so mine will be faster (if it is unordered)

Answer 3

What’s a good way to achieve it in PHP