我们有两个未排序的数组，每个数组的长度为 n。这些数组包含随机整数。
如何在Θ(n*logn) 时间内找出这两个数组是否有共同元素？
不允许排序。
最佳答案
设 A 和 B 为未排序的数组，长度均为 n。 您可以按照@amit 的建议使用哈希表；但是，还有一种更快的算法。 由于 Card(A) = Card(B)，快速交集算法是使用 Bloom filter存储集合，然后通过按位与运算实现交集。这仍然需要 O(n)，但对于隐藏在渐近符号中的常量和低阶项而言，这是一个更好的结果。
关于arrays - (算法)在不排序的情况下，在 Θ(n*logn) 时间内查找两个未排序的数组是否有共同元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13669514/