Найти похожие строки в 3 двумерных массивах

Question

Каков наилучший подход для решения следующей проблемы в Java? Существует 3 двумерных массива с одинаковым количеством строк и столбцов:

Array1:
[1]: {1, 2, 3}
[2]: {2, 2, 4}
[3]: {1, 1, 1}

Array2:
[1]: {1, 2, 0}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

Array3:
[1]: {1, 1, 1}
[2]: {1, 2, 3}
[3]: {1, 0, 1}

Мне нужно выяснить индексы строк , которые существуют во всех массивах. В приведенном выше примере ответ должен быть: [1], [2], [2]

Array1 [1] : {1, 2, 3}

array2: [2] : {1, 2, 3}

Array3: [2] : {1, 2, 3}

ОБНОВЛЕНИЕ: есть ли встроенная функция для этого? Или цикл FOR - это уникальное решение?

Answer 1

Проверьте этот код:

ArrayList<Integer[]> arr1 = new ArrayList<Integer[]>();
    arr1.add(new Integer[]{1,2,3});
    arr1.add(new Integer[]{2,2,5});
    arr1.add(new Integer[]{1,1,1});

    ArrayList<Integer[]> arr2 = new ArrayList<Integer[]>();
    arr2.add(new Integer[]{1,2,0});
    arr2.add(new Integer[]{1,2,3});
    arr2.add(new Integer[]{1,0,1});

    ArrayList<Integer[]> arr3 = new ArrayList<Integer[]>();
    arr3.add(new Integer[]{1,1,1});
    arr3.add(new Integer[]{1,2,3});
    arr3.add(new Integer[]{1,0,1});


    for (int r = 0 ; r < arr1.length() ; r++) {
        for(int s = 0 ; s < arr2.length() ; s++){
            for(int t = 0 ; t < arr3.length() ; t++){
                if(Arrays.deepEquals(arr1.get(r), arr2.get(s))){

                }else
                {
                    continue;
                }
                if(Arrays.deepEquals(arr1.get(r), arr3.get(t))){
                    System.out.println(r + " " + s + " " +t);;  
                }
            }

        }
    }

Answer 2

AFAIK для этого нет встроенной функции.

Вам нужно написать свою собственную функцию для ее реализации (используя цикл for).

опубликовать некоторый код, чтобы показать, что вы пробовали, если он не работает в основном ИЛИ для оптимизации.

Answer 3

Прежде всего, напишите функцию с именем AreRowsEqual(), которая сравнивает две строки.Итак, теперь проблема была переформулирована как Find similar elements in 3 arrays.

Во-вторых, попытайтесь придумать решение, которое было бы наиболее близким к тому, что вы уже знаете, основываясь на предыдущих знаниях: найти равные элементы в двух массивах.Вам нужен двойной вложенный цикл.Итак, чтобы найти равные элементы в трех массивах, вам понадобится тройной вложенный цикл, верно?

Хорошо, теперь вычеркните это как плохое, плохое, плохое решение, потому что его временная сложность составляет O (n ^ 3) .Мы должны быть в состоянии добиться большего успеха.

Подумайте об этом: чтобы элемент был похож во всех трех массивах, сначала он должен быть похожим среди первых двух;затем он должен быть похожим среди следующих двух.Сложность такого алгоритма будет сродни O (x * n) , где x - количество массивов.Намного лучше, верно?(Я не могу точно понять, что O () будет, помочь кому-нибудь?) РЕДАКТИРОВАТЬ: оказывается, это O ((n ^ 2) * (x-1)), что многолучше, чем O (n ^ 3), когда n> x - END EDIT Это, кстати, позволяет забыть о требовании строго 3 массивов и просто рассмотреть количество x массивов.

Я написал подход, который получил одно голосование, а затем я понял, что это не сработает, и удалил его.Это еще одна попытка, которая, я считаю, сработает:

Создайте двумерный массив целых чисел.Мы будем называть это «матрицей».Эта матрица будет иметь x столбцов, а количество строк будет числом строк вашего первого массива.(Да, это будет работать, даже если ваши массивы имеют разную длину.) Числа в ячейках этой матрицы будут соответствовать индексам строк.Так, например, после того, как алгоритм, который я описываю, заканчивается, строка { 1, 3, 2 } в матрице скажет нам, что строка 1 первого массива соответствует строке 3 второго массива и строке 2 третьего массива.Мы будем использовать -1 для обозначения «нет совпадения».

Итак, первый столбец матрицы необходимо инициализировать с индексами всех строк вашего первого массива, то есть с числами 0, 1, 2, ... n где n - количество элементов в первом массиве.

Для каждого дополнительного массива заполните его столбец в матрице следующим образом: выполните цикл по каждой строке текущего столбца в матрице и вычислите ячейку следующим образом: если соответствующая ячейка предыдущего столбца была -1, несите -1 в эту камеру.В противном случае найдите строку в текущем массиве, которая соответствует соответствующей строке предыдущего массива, и, если она найдена, сохраните ее индекс в этой ячейке.В противном случае сохраните -1 в этой ячейке.

Повторите для всех ваших массивов, то есть для всех столбцов в матрице.В конце концов, ваши подходящие строки - это те, которые не имеют -1 в последнем столбце матрицы.

Если вы действительно заботитесь об эффективности, вы можете поступить как Джон Б.предложил и напишите неизменный класс с именем Row, который инкапсулирует (содержит ссылку на) строку и реализует hashCode() и equals().equals() здесь можно реализовать с помощью Arrays.deepEquals().В Arrays также может быть какое-то лакомство, называемое deepHashCode(), иначе вам придется бросить свой собственный.

Answer 4

Я хотел бы сделать следующее:

• Создать класс, который принимает строку в массиве и реализует hashcode и equals.
• Вставить каждую строку (завернутый ввышеуказанный класс) в первых двух массивах на два HashMaps
• для каждой строки в последнем массиве определите, существуют ли они в HashMaps

Edit # 2,понял, что отображение нужно будет обратить вспять.

private Map<MyClass, Integer> map(int[] array){
  Map<MyClass, Integer> arrayMap = new HashMap<>();
  for (int i; i<array.length; i++)
        arrayMap.put(new MyClass(array[i]), i);
}

private mySearch(){
   int[] array1, array2, array3;

   Map<MyClass, Integer> map1 = map(array1);
   Map<MyClass, Integer> map2 = map(array2);

   for (int i=0; i<array3.lenght; i++){
      MyClass row = new MyClass(array3[i]);
      Integer array1Row = map1.get(row);
      Integer array2Row = map2.get(row);

      if (array1Row != null && array2Row != null){
         // Matching rows found
      }
   }
}

Answer 5

1. Напишите метод, который принимает два аргумента: двумерный массив для поиска, одномерную строку массива. Метод возвращает -1, если совпадение не найдено, в противном случае возвращает индекс совпадающей строки.

2. Для каждой строки первого массива: 2а. Вызовите метод, передавая строку из первого массива и Array2. 2b. Если 2a возвращает> 0, вызовите метод, передавая ту же строку и Array3

3. Если 2b возвращает> 0, выведите возвращенные индексы.

Answer 6

Проверка Arrays.deepEquals () метод. Он проверит, что два массива равны или нет.