arrays - （算法）查找两个未排序的数组在 Θ(n*logn) 时间内是否有任何共同元素而不进行排序？

Question

我们有两个未排序的数组，每个数组的长度为n. 这些数组包含随机整数。如何及时查找这两个数组是否有任何共同的元素Θ(n*logn)？

不允许排序。

Answer 1

让A和B成为您的未排序数组，长度均为n。您可以按照@amit 的建议使用哈希表；但是，还有一个更快的算法。由于Card(A) = Card(B)，快速交集算法是使用布隆过滤器来存储集合，然后使用按位与运算实现交集。这仍然需要O(n)，但对于隐藏在渐近符号中的常数和低阶项，它是一个更好的结果。