检查两个很长的数组是否至少有一个公共元素的最快（运行时）方法？

Question

我正在尝试检查两个数组是否至少有一个公共元素，我已经尝试过一种解决方案但速度不够快，它基本上由两个嵌套循环组成，代码如下：

boolean oneElementChecker(int[] pArray1, int[] pArray2)
    while (i < pArray1.length) {

      j = 0;

      if (sameValueChecker)
        break;

      while (j < pArray2.length) {

        if ((pArray1[i] == pArray2[j]))
          sameValueChecker = true;

        j++;
      }

      i++;
    }

    return !sameValueChecker;

我需要知道是否有方法可以加快这项任务。

Answer 1

如果你的意思是在短运行时快速，除非使用预先排序的数组，否则我认为没有更快的方法。

如果您的意思是快速，因为占用更少的行（我猜打字速度更快），使用 Java 流的更优雅的方式是：

int[] array1 = ...  
int[] array2 = ...

boolean shared = Arrays.stream(array1).anyMatch(I -> Arrays.asList(array2).contains(i));

Answer 2

如果 space 不是问题，那么我可能会建议使用 HASHING。

首先，创建数组 pArray1 元素的哈希集。（这将在 O(n) 时间复杂度内完成）。

然后，开始遍历第二个数组，对每个元素在hashset中查找是否存在（注意：hashset查找是O(1)操作）。继续遍历，直到找到 hashset 中的元素或第二个数组 pArray2 到达其末尾。

因此，本质上使用哈希，您将消除嵌套循环，最终时间复杂度将是 O(n) (O(n) + O(n) )。

Answer 3

对于未排序的数组，接受的答案是更好的选择，但如果数组已排序，请按照以下步骤操作，比如数组是 A[m] 和 B[n]

1：分别为数组A和B初始化索引i = 0和j = 0 2: 然后做如下

if(A[i] == B[i]) {
 //print the common element
} else if(A[i] < B[i]){
 i++  //increment i
} else {
 j++; //increment j
}

这样你就可以在 O(m+n) 中找到排序数组中的公共元素。尽管您也可以在对未排序的数组进行排序后使用这种方法，这可能需要 O(mLogm + nLogn) 时间复杂度，因此最好使用散列

Answer 4

如果可以使用Collections.disjoint()

boolean result = disjoint(asList(array1), asList(array2));

如果两个指定的集合没有共同的元素，

result 为真。

检查两个很长的数组是否至少有一个公共元素的最快（运行时）方法？

Fastest (runtime) way to check if two very long arrays have at least one common element?

java

arrays

processing