java:如何检查两个数组是否包含公共元素？

Question

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

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

提前致谢!

Answer 1

如果数组很小,那么带有嵌套for循环的解决方案(例如@ scaryrawr)将表现最佳.

如果阵列足够大,那么O(N^2)上述解决方案的复杂性将是有问题的.解决方案是使用HashSet; 例如

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)临时空间.

如果字符的范围有限,那么您可以使用a BitSet而不是a HashSet.这也将大致O(N)在时间和空间上,尽管角色的范围也是复杂性的一个因素,所以称之为O(N)过度简化.

但我们可能"过度思考"这一点.最好的建议可能是实现简单的操作,如果怀疑性能是一个真正的问题,那么对其进行分析以避免浪费你的时间进行不必要的优化.