Самый эффективный способ найти дубликаты в связанном списке связанных списков строк - java

Question

Предположим, у нас есть связанный список связанных списков строк.

LinkedList<LinkedList<String>> lls = new LinkedList<LinkedList<String>>(); 
LinkedList<String> list1 = new LinkedList<String>(Arrays.asList("dog", "cat", "snake")); 
LinkedList<String> list2 = new LinkedList<String>(Arrays.asList("donkey", "fox", "dog")); 
LinkedList<String> list3 = new LinkedList<String>(Arrays.asList("horse", "cat", "pig")); 
lls.add(list1); 
lls.add(list2); 
lls.add(list3); 

Как вы можете видеть, этот 3 связанный список строк отличается, но также имеет некоторые общие элементы. Моя цель - написать функцию, которая сравнивает каждый список с остальными и возвращает TRUE, если есть хотя бы один общий элемент (собака в списке1 и list2), FALSE в противном случае.

Я думаю, что первое, что мне нужно, это сравнить все возможные перестановки между списками, а сравнение между списками - это элемент за элементом. Я не уверен, что это самый эффективный подход. Не могли бы вы предложить идею, которая в конечном итоге наиболее эффективна?

Answer 1

Предполагая, что данные списки не должны быть изменены путем удаления элементов или их сортировки (что, кстати, имеет сложность O (nlogn)), вам в основном нужна одна функция как «строительный блок» для реального решения. А именно, функция, которая проверяет, содержит ли одна коллекция любой элемент, который содержится в другой коллекции.

Конечно, это можно решить, используя Collection#contains во второй коллекции. Но для некоторых коллекций (в частности, для списков) это имеет O (n), а общее время выполнения проверки будет O (n * n).

Чтобы избежать этого, вы можете создать Set, который содержит все элементы второй коллекции. Для Set гарантируется contains метод O (1).

Затем, фактическая проверка может быть сделано удобно, с Stream#anyMatch:

containing.stream().anyMatch(e -> set.contains(e)) 

Так что полный пример может быть

import java.util.Arrays; 
import java.util.Collection; 
import java.util.LinkedHashSet; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Set; 

public class DuplicatesInLinkedLists 
{ 
    public static void main(String[] args) 
    { 
     LinkedList<LinkedList<String>> lls = 
      new LinkedList<LinkedList<String>>(); 
     LinkedList<String> list1 = 
      new LinkedList<String>(Arrays.asList("dog", "cat", "snake")); 
     LinkedList<String> list2 = 
      new LinkedList<String>(Arrays.asList("donkey", "fox", "dog")); 
     LinkedList<String> list3 = 
      new LinkedList<String>(Arrays.asList("horse", "cat", "pig")); 
     lls.add(list1); 
     lls.add(list2); 
     lls.add(list3); 

     checkDuplicates(lls); 
    } 

    private static void checkDuplicates(
     List<? extends Collection<?>> collections) 
    { 
     for (int i = 0; i < collections.size(); i++) 
     { 
      for (int j = i + 1; j < collections.size(); j++) 
      { 
       Collection<?> ci = collections.get(i); 
       Collection<?> cj = collections.get(j); 
       boolean b = containsAny(ci, cj); 
       System.out.println(
        "Collection " + ci + " contains any of " + cj + ": " + b); 
      } 
     } 
    } 

    private static boolean containsAny(Collection<?> containing, 
     Collection<?> contained) 
    { 
     Set<Object> set = new LinkedHashSet<Object>(contained); 
     return containing.stream().anyMatch(e -> set.contains(e)); 
    } 
} 

---

Примечание стороны: код, который Вы отправили почти конечно, не имеет смысла в текущей форме.Декларация и создание списков обычно должны полагаться на List:

List<List<String>> lists = new ArrayList<List<String>>(); 
lists.add(Arrays.asList("dog", "cat", "snake"); 
... 

Если элементы списка должны мне изменяемый, то вы могли бы написать

lists.add(new ArrayList<String>(Arrays.asList("dog", "cat", "snake")); 

или, аналогично, используйте LinkedList вместо ArrayList, но для набросанного варианта использования, я не могу себе представить, почему должна быть веская причина для намеренного использования LinkedList вообще ...

Answer 2

Добавить все элементы во все списки в один список, а затем отсортировать его (Collections.sort). Затем проведите по ней и проверьте наличие дубликатов.

E.g.

ArrayList<String> list = new ArrayList<>(); 
list.addAll(list1); // Add the others as well 
Collections.Sort(list); 
for (String s : list) { 
    If (the item is the same as the previous item) { 
     return true; 
    } 
} 

Answer 3

Использование retainAll()

for (final LinkedList<String> ll : lls) 
    { 
     list1.retainAll(ll); 
    } 
    System.out.println("list1 = " + list1); 

Answer 4

LinkedList не лучшая коллекция для обнаружения дубликатов. Если можно, попробуйте использовать HashSet, но если вы не можете этого сделать, вы все равно можете поместить все элементы из списка для установки. Hashset содержит элементы без дубликатов, поэтому, если есть дублированный элемент в размере списка, hashset будет содержать меньше элементов, чем все списки.

Answer 5

Предполагая, что вы хотите использовать LinkedLists и не разрешено преобразовывать в другую структуру данных, то вы можете создать метод, который принимает переменную сумму LinkedLists. Оттуда вы хотите захватить все уникальные комбинации LinkedLists, а затем сравнить все уникальные элементы между этими связанными списками, если вы найдете общий элементный знак, что пара связанных списков является общей. Как вы хотите отслеживать/возвращать данные (набор пар связанных списков, которые имеют общий элемент, например) зависит от того, как должен выглядеть ваш вывод, но это общая структура кода, который я бы использовал.