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

Let's say I have the following two arrays:

假设我有以下两个数组：

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

I would like to take the first value of array a - 1 - and see if it is contained in array b. So, I would get that the '1' from a is in b even if it is not in the same position. Once I have gone through the comparison for the first element in a, I move on to the next number in array a and continue the process until I have completely gone through the first array.

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

I know I need to do some looping (possibly nested?) but I can't quite figure out how I stick with just the first number in array a while looping through all the numbers in array b.

我知道我需要做一些循环（可能是嵌套的？）但是我无法弄清楚我是如何坚持数组中的第一个数字，同时循环遍历数组b中的所有数字。

This seems to be fairly simple I just can't get my head around it...

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

5 个解决方案

#1

These solutions all take O(n^2) time. You should leverage a hashmap/hashset for a substantially faster O(n) solution:

这些解决方案都需要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!   
    }
}

#2

Yes, you need two loops, and yes, nested.

是的，你需要两个循环，是的，嵌套。

pseudocode it will look like:

伪代码看起来像：

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

Now everything you need is to translate it to Java. Since it sounds like a homework or some exercise you should do it by yourself.

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

Also, think about what output you need. If you just need a true/false whether a and b have some common values, then you can exit the loops as soon as you find the first match. If instead you need to count the number of common elements between the arrays, you'll need to throw a counter into that set of nested loops. I'll leave it up to you to figure out that portion.

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

#3

You just need two nested for loops

你只需要两个嵌套的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
        }
    }
}

What this does is go to the first value of a and compare to each value in b, then go to the next value of a and repeat.

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

#4

Since you haven't got this tagged as homework, I'll give you the benefit of the doubt. As you said you'll need two loops; loop foreach int in a[] and foreach int in b[]. Then just compare the two values at each iteration, which gives you the simple code of:

既然你没有把这个标记为作业，我会给你怀疑的好处。正如你所说，你需要两个循环;循环foreach int in []和foreach int in b []。然后只需比较每次迭代时的两个值，它们为您提供简单的代码：

for (int x : a) {
   for (int y : b) {
      if (x == y) {
         System.out.println("a[] and b[] both contain " + x);
      }
   }
}

#5

Depending on the data (its size, whether every value is unique, etc) and what you're trying to get from it (ie, whether each element of a is in b, or also its index in b), it may be beneficial to do a bit of overhead work before you do the meat of it. For instance, if you sort both arrays (which you'll only need to do once), you can start the inner loop where you stopped it last (since you know that you're looking for a number >= the one you looked for last, so it's got to be at this index or greater), and you can also stop the inner loop sooner (since you know that if you're looking for X and you haven't found it before seeing a value > X, then X isn't there). Another approach would be to load both values into a Set, which you can now probe efficiently.

根据数据（它的大小，每个值是否是唯一的等）以及你想从中获得的数据（即，a的每个元素是否在b中，或者在b中的索引），它可能是有益的在做它之前做一些开销工作。例如，如果你对两个数组进行排序（你只需要做一次），你就可以开始最后停止它的内部循环（因为你知道你正在寻找一个数字> =你寻找的数字最后，所以它必须在这个索引或更高），你也可以更快地停止内循环（因为你知道如果你正在寻找X而你在看到值> X之前没有找到它，那么X不存在）。另一种方法是将两个值加载到Set中，您现在可以有效地进行探测。

#1