Поиск повторяющихся значений между двумя массивами

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.Поскольку это звучит как домашнее задание или какое-то упражнение, вы должны сделать это самостоятельно.

Кроме того, подумайте, какой результат вам нужен.Если вам просто нужно значение true / false, если 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 и повторите.

Answer 4

В зависимости от данных (их размера, уникальности каждого значения и т. Д.) И того, что вы пытаетесь получить из них (т. Е. Находится ли каждый элемент a в b или также его индекс в b), он может быть полезно выполнить небольшую работу над головой, прежде чем делать суть. Например, если вы сортируете оба массива (что вам нужно сделать только один раз), вы можете запустить внутренний цикл, где вы остановили его в последний раз (так как вы знаете, что ищете число> = тот, который вы искали последний, так что он должен быть с этим индексом или выше), и вы также можете быстрее остановить внутренний цикл (поскольку вы знаете, что если вы ищете X и не нашли его до того, как увидели значение> X, то Х там нет). Другой подход заключается в загрузке обоих значений в набор, который теперь можно эффективно проверять.

Answer 5

Так как вы не отметили это как домашнее задание, я дам вам преимущество сомнения. Как вы сказали, вам понадобятся две петли; цикл foreach int в a[] и foreach int в b[]. Затем просто сравните два значения на каждой итерации, что даст вам простой код:

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