我们有两个未排序的数组，每个数组的长度为 n 。这些数组包含随机整数。如何找到这两个数组在Θ(n*logn)时间内是否有任何共同元素？
不允许排序。
设 A 和 B 是你的未排序数组，长度均为 n。您可以按照@amit的建议使用哈希表;但是，有一种更快的算法。由于 Card（A） = Card（B），因此快速交集算法是使用 Bloom 过滤器来存储集合，然后通过按位 AND 运算实现交集。这仍然需要 O（n），但对于隐藏在渐近符号中的常量和低阶项，这是一个更好的结果。