在两个数组之间查找重复值

Question

假设我有以下两个数组:

int[] a = [1,2,3,4,5];
int[] b = [8,1,3,9,4];

我想取数组的第一个值a- 1 - 并查看它是否包含在数组中b.所以,我会得到从"1" a是b即使它是不是在同一个位置.一旦我完成了第一个元素的比较a,我就转到数组中的下一个数字a并继续该过程,直到我完全通过第一个数组.

我知道我需要做一些循环(可能是嵌套的？)但我无法弄清楚如何a在循环遍历数组中的所有数字时坚持数组中的第一个数字b.

这似乎相当简单我只是无法理解它...

Answer 1

这些解决方案都需要O(n ^ 2)时间.您应该利用hashmap/hashset来获得更快的O(n)解决方案:

void findDupes(int[] a, int[] b) {
    HashSet<Integer> map = new HashSet<Integer>();
    for (int i : a)
        map.add(i);
    for (int i : b) {
        if (map.contains(i))
            // found duplicate!   
    }
}

Answer 2

是的,你需要两个循环,是的,嵌套.

伪代码看起来像:

for each in A do
    for each in B do
       if (current item of A equals to current item of B)
           say yes!
    done
done

现在你需要的一切就是把它翻译成Java.因为它听起来像是一个家庭作业或一些运动,你应该自己做.

另外,请考虑您需要的输出.如果你只需要一个真/假是否a和b有一些共同的价值观,那么你可以只要你找到的第一个匹配退出循环.相反,如果需要计算数组之间的公共元素的数量,则需要将计数器抛入该组嵌套循环中.我会把它留给你来弄清楚那一部分.

Answer 3

你只需要两个嵌套的for循环

for(int i = 0; i < a.length; i++)
{
    for(int j = 0; j < b.length; j++)
    {
        if(a[i] == b[j])
        {
            //value is in both arrays
        }
    }
}

这样做是转到a的第一个值并与b中的每个值进行比较,然后转到a的下一个值并重复.