java - 两个大小为 100 万的数组中的第一个公共(public)数字

Question

我有两个非常大的整数数组，每个数组的大小大约为 100 万。我必须找到两个数组中都存在的第一个整数。

我试着用一组来做到这一点。

(1)同时遍历每个数组，将两个数组的元素插入集合。

(2) 每当集合拒绝接受那是第一个交集。

int Solution(int A[], int B[])
{
    Set s = new HashSet();
    for (int i = 0 ; ; i++)
    {
        if ( i < A.length )
        {
            if( !s.Add(A[i]) )
                System.out.println(A[i]);
        }
        if ( i < B.length )
        {
            if( !s.Add(B[i]) )
                System.out.println(B[i]);
        }
    }
}

我们能否改进此解决方案以降低时间复杂度？

谢谢

Answer 1

in case of A={1,2,3} B={2,1,3} 1 is the number because it's occur first in A

这意味着您的算法在某些情况下不会产生正确的答案。考虑以下数据:

A = {1, 2, 3, 4, 5, 6, 7}
B = {7, 2, 3, 4, 5, 6, 1}

您的算法将返回 2 而不是 1，因为在第二次插入两个集合后会检测到 2，而您需要将 B 迭代到末尾才能检测到 1。

根据您的规范为您提供正确解决方案的一种方法是将 B 的所有元素加载到哈希集中，然后迭代 A 直到您在由 B 中的数字组成的集合中获得成功。这种方法是 O(N_a+N_b).

Set<Integer> bSet = new HashSet<Integer>();
for (int n : B) {
    bSet.add(n);
}
for (int n : A) {
    if (bSet.contains(n)) {
        return n;
    }
}
// If you get here, arrays have no elements in common