java - 检查两个非常长的数组是否至少有一个公共(public)元素的最快(运行时)方法？

Question

我正在尝试检查两个数组是否至少有一个公共(public)元素，我已经尝试了一种解决方案，但它不够快，它本质上由两个嵌套循环组成，这是代码:

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

如果空间不是问题，那么我可能会建议使用哈希。

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

然后，开始遍历第二个数组，并为每个元素在哈希集中查找是否存在(注意:哈希集查找是 O(1) 操作)。继续遍历，直到在哈希集中找到一个元素或第二个数组 pArray2 到达其末尾。

因此，本质上使用散列，您可以消除嵌套循环，最终时间复杂度将为 O(n) (O(n) + O(n) )。