Искать в ArrayList

Question

У меня есть 2 ArrayList, которые имеют Array of Strings в качестве «компонента».Я хочу найти «компоненты», первый элемент которых одинаков в обоих списках 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();
            }
        }
    }

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

Answer 1

Используйте 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)

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

Answer 2

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

Answer 3

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

One.retainAll(Two)

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

Answer 4

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

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

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