两个大小为100万的数组中的第一个常见数字

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

在A={1,2,3} B={2,1,3}1的情况下是数字,因为它首先出现在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