Блог

У меня есть 2 ArrayLists, которые содержат массив строк в качестве «компонента». Я хочу найти «компоненты», первый элемент которых одинаков в обоих ArrayLists. Чтобы было более понятно:

 ArrayList One
first component => {"0", "zero"}
second component => {"1", "one"}
ArrayList Two
first component => {"1", "uno"}
second component => {"2", "two"}
  

Я хотел бы выполнить цикл по ArrayList Two и найти {«1», «uno»}.
Пока что у меня есть вложенный цикл, который перебирает первый массив, а затем проверяет текущий компонент для каждого компонента в ArrayList Two.

     for(int i=0; i<One.size(); i  )
    {
        for(int j=0; j<Two.size(); j  )
        {
            if( fileOne.get(i)[0].equals( Two.get(j)[0] ) )
            {
                System.out.print( Two.get(j)[0] " " );
                System.out.print( Two.get(j)[1] );
                System.out.println();
            }
        }
    }
  

Я думаю, что должно быть лучшее решение. Любая помощь

Используйте HashSet.

 Set<String> set = new HashSet<String>()
for(int i=0; i<One.size(); i  ) {
  set.add(fileOne.get(i)[0]);
}

for(int i=0; i<Two.size(); i  ) {
  String component[] = Two.get(j)
  if(set.contains(component[0])) {
    System.out.print( component[0] " " );
    System.out.print( component[1] );
    System.out.println();
   }
}
  

Примечание: Список не будет работать в этом случае, потому что поиск в списках равен O (N). Поиск в HashSets равен O (1), поэтому построение набора (первый цикл) равно O (N). Тогда просмотр вашего второго массива равен O (M), а каждый поиск равен O (1).

В целом, это становится O (N) ( O (M) * O (1) ) = O (N M)

Редактировать: для комментариев Ted.

Вы могли бы попробовать использовать hashmap. Инициализируйте его из первого ArrayList путем сопоставления первого элемента каждого компонента с компонентом (или индексом компонента). Затем для каждого компонента второго ArrayList вы можете выполнить поиск по первому элементу каждого компонента, чтобы найти соответствующий компонент (или обнаружить, что его нет, когда он возвращается null ).

Используйте два набора хэшей и метод retainAll таким образом, чтобы:

 One.retainAll(Two)
  

С точки зрения сложности лучше — только O (n m) против вашего O (n * m). И с точки зрения удобства чтения и сопровождения также лучше. Обратите внимание, что retainAll это изменит hashset One , если вы не хотите, чтобы поведение создавало третью копию.

(отредактировано в ответ на комментарий Ted)

Без работы по инициализации, такой как сортировка / хеширование или поддержание отсортированного / хэшированного списка, лучшего решения не существует, оптимальным решением является O (n * m), которое у вас есть. Это оптимальное решение, потому что вам нужно сравнивать каждый элемент с любым другим элементом.

Я должен также упомянуть, что в определенных сценариях может быть разумнее сохранить список отсортированным. Тогда вместо сравнения каждого элемента вы могли бы использовать двоичный поиск или что-то в этом роде. Но без предварительной сортировки вашего списка, да, вам придется сравнить все элементы. Я считаю, что наилучшее возможное время сортировки — O (nlgn). Затем после этого процесса сортировки вам все равно придется искать свой элемент в отсортированном списке, но поиск по отсортированному списку может быть быстрее, чем поиск по несортированному.