Java：如何检查两个数组是否包含公共元素？[关闭]

Question

有没有什么简单的方法可以检查两个数组是否包含任何公共元素？这合适吗？数组包含类型char。

Arrays.asList(encryptU).contains(Ualpha[randNum]));

提前道谢！

Answer 1

如果数组很小，那么具有嵌套for循环的解决方案（例如@ScaryRawr's)将会执行得最好。

如果数组足够大，那么上述解决方案的O(n^2)复杂度就会有问题。解决方案是使用哈希集；例如。

HashSet<Character> tmp = new HashSet<Character>();
for (char ch : arr1) {
    tmp.add(ch);
}
for (char ch : arr2) {
    if (tmp.contains(ch)) {
        // elements in common!!
    }
}

这是时间上的O(N)，尽管比例常数相当大。（我认为您需要数组大小的乘积为20或30，这样才能比嵌套循环解决方案更快...但这只是猜测。）此外，这需要O(N)临时空间。

如果字符的范围有限，则可以使用bitset而不是hashset。这在时间和空间上也大致是O(N)，尽管字符的范围也是复杂度的一个因素，所以称它为O(N)是一种过度简化。

但我们对此很可能是“想多了”。最好的建议可能是实现一些简单的东西，如果怀疑性能是一个真正的关注点，那么就对其进行分析，以避免不必要的优化浪费您的时间。