wake-up-neo.com

Einfache Möglichkeit zu finden, ob zwei verschiedene Listen genau dieselben Elemente enthalten?

Was ist der einfachste Weg, um herauszufinden, ob zwei Listen in den Standard-Java-Bibliotheken genau dieselben Elemente enthalten? 

Es sollte keine Rolle spielen, ob die beiden Listen dieselbe Instanz sind oder nicht, und es sollte keine Rolle spielen, ob die Typparameter der Listen unterschiedlich sind.

z.B.

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

Es gibt wahrscheinlich etwas, das mir ins Gesicht starrt, das ich kenne :-)


BEARBEITEN: Um zu klären, habe ich nach den EXACT-Elementen und der Anzahl der Elemente gesucht.


EDIT: Danke für die offensichtliche Antwort, die ich nicht sehen konnte :-)

Obwohl alle bisherigen Antworten richtig sind, sind einige zutreffender als andere. Daher werde ich eine Weile auf die beste abgerundete Antwort warten, bevor ich sie annehme.

207
Grundlefleck

Wenn Sie sich um die Reihenfolge kümmern, verwenden Sie einfach die Methode equals:

list1.equals(list2)

Aus dem Javadoc:

Vergleicht das angegebene Objekt mit diese Liste für die Gleichheit. Gibt true zurück wenn und nur dann, wenn das angegebene Objekt .__ ist. auch eine Liste, beide Listen haben das gleiche Größe und alle entsprechenden Paare von Elemente in den beiden Listen sind gleich . (Zwei Elemente e1 und e2 sind gleich, wenn (E1 == null? E2 == null: E1.equals (e2)).) Mit anderen Worten: zwei Listen werden als gleich definiert, wenn sie enthalten die gleichen Elemente in derselben Auftrag. Diese Definition stellt sicher, dass Die Equals-Methode funktioniert einwandfrei über verschiedene Implementierungen von die Liste Schnittstelle.

Wenn Sie unabhängig von der Reihenfolge prüfen möchten, können Sie alle Elemente in Sets kopieren und in den resultierenden Sets Gleichheitszeichen verwenden:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

Eine Einschränkung dieses Ansatzes besteht darin, dass nicht nur die Reihenfolge, sondern auch die Häufigkeit doppelter Elemente ignoriert wird. Wenn list1 beispielsweise ["A", "B", "A"] und list2 ["A", "B", "B"] wäre, würde der Set-Ansatz sie als gleichwertig betrachten.

Wenn Sie gegenüber der Reihenfolge unempfindlich sein müssen, aber die Häufigkeit der Duplikate berücksichtigen möchten, haben Sie folgende Möglichkeiten:

298

Ich habe ein paar Sachen in Kommentaren gepostet, die meiner Meinung nach eine eigene Antwort erfordern.

Wie jeder hier sagt, hängt die Verwendung von equals () von der Reihenfolge ab. Wenn Sie sich nicht für die Bestellung interessieren, haben Sie 3 Optionen.

Option 1

Verwenden Sie containsAll(). Diese Option ist meiner Meinung nach nicht ideal, da sie die Leistung im ungünstigsten Fall bietet, O (n ^ 2).

Option 2

Hier gibt es zwei Varianten:

2a) Wenn Sie die Reihenfolge Ihrer Listen nicht beibehalten möchten, verwenden Sie Collections.sort() in beiden Listen. Verwenden Sie dann die equals(). Dies ist O (nlogn), weil Sie zwei Sortierungen durchführen und dann einen Vergleich von O(n).

2b) Wenn Sie die Reihenfolge der Listen pflegen müssen, können Sie zuerst beide Listen kopieren. DANN können Sie die Lösung 2a in beiden kopierten Listen verwenden. Dies kann jedoch uninteressant sein, wenn das Kopieren sehr teuer ist.

Dies führt zu:

Option 3

Wenn Ihre Anforderungen mit Teil 2b identisch sind, ist das Kopieren jedoch zu teuer. Sie können ein TreeSet verwenden, um die Sortierung für Sie durchzuführen. Legen Sie jede Liste in einem eigenen TreeSet ab. Es wird im Set sortiert und die ursprünglichen Listen bleiben erhalten. Führen Sie dann einen equals()-Vergleich für beide TreeSets durch. Die TreeSetss können in der Zeit O(nlogn) erstellt werden, und die equals() ist O (n).

Treffen Sie Ihre Wahl :-).

EDIT: Ich habe fast den gleichen Vorbehalt vergessen, auf den Laurence Gonsalves hinweist. Die TreeSet-Implementierung entfernt Duplikate. Wenn Sie sich für Duplikate interessieren, benötigen Sie eine Art sortiertes Multiset.

78
Tom

Wenn Sie Apache Commons Collections verwenden (oder gerne verwenden), können Sie CollectionUtils.isEqualCollection verwenden, die "true" zurückgibt, wenn die angegebenen Collections genau dieselben Elemente mit genau denselben Kardinalitäten enthalten.

12
megaflop

Ich weiß, dass dies ein alter Thread ist, aber keine der anderen Antworten hat meinen Anwendungsfall vollständig gelöst (Guava Multiset könnte dasselbe tun, aber hier gibt es kein Beispiel). Bitte entschuldigen Sie meine Formatierung. Ich bin immer noch neu beim Posten auf Stack-Tausch. Lassen Sie mich außerdem wissen, wenn Fehler auftreten 

Nehmen wir an, Sie haben List<T> a und List<T> b und möchten mit den folgenden Bedingungen prüfen, ob sie gleich sind:

1) O(n) erwartete Laufzeit
2) Gleichheit ist definiert als: Für alle Elemente in a oder b ist die Anzahl, wie oft das Element in a auftritt, gleich der Anzahl, wie oft das Element in b auftritt. Elementgleichheit wird als T.equals () definiert

private boolean listsAreEquivelent(List<? extends Object> a, List<? extends Object> b) {
    if(a==null) {
        if(b==null) {
            //Here 2 null lists are equivelent. You may want to change this.
            return true;
        } else {
            return false;
        }
    }
    if(b==null) {
        return false;
    }
    Map<Object, Integer> tempMap = new HashMap<>();
    for(Object element : a) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            tempMap.put(element, 1);
        } else {
            tempMap.put(element, currentCount+1);
        }
    }
    for(Object element : b) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            return false;
        } else {
            tempMap.put(element, currentCount-1);
        }
    }
    for(Integer count : tempMap.values()) {
        if(count != 0) {
            return false;
        }
    }
    return true;
}

Die Laufzeit ist O(n), da wir O (2 * n) -Einfügungen in eine Hashmap vornehmen und O (3 * n) -Hashmap auswählen. Ich habe diesen Code noch nicht vollständig getestet.

//Returns true:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A"));
listsAreEquivelent(null,null);
//Returns false:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),null);
6
Andrew

Sehr spät zur Party, aber ich wollte diese null sichere Überprüfung hinzufügen:

Objects.equals(list1, list2)
5
Reimeus

Versuchen Sie es mit dieser Version, bei der es nicht erforderlich ist, dass die Reihenfolge identisch ist, jedoch mehrere gleiche Werte unterstützt werden. Sie stimmen nur überein, wenn jeder die gleiche Menge eines beliebigen Werts hat.

public boolean arraysMatch(List<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}
4
Lee Meador

Toms Antwort ist ausgezeichnet Ich stimme voll und ganz mit seinen Antworten überein

Ein interessanter Aspekt dieser Frage ist, ob Sie den Typ List selbst und seine inhärente Reihenfolge benötigen.

Ist dies nicht der Fall, können Sie auf Iterable oder Collection zurückgreifen, wodurch Sie bei der Weitergabe von Datenstrukturen, die nach Einfügezeit sortiert sind, eine gewisse Flexibilität haben, und nicht zu dem Zeitpunkt, zu dem Sie überprüfen möchten.

Wenn die Reihenfolge keine Rolle spielt (und Sie keine doppelten Elemente haben), sollten Sie eine Set verwenden.

Wenn die Reihenfolge wichtig ist, aber durch die Einfügungszeit definiert ist (und Sie keine Duplikate haben), betrachten Sie eine LinkedHashSet, die wie ein TreeSet ist, aber nach Einfügungszeit geordnet ist (Duplikate werden nicht gezählt). Dadurch erhalten Sie auch O(1) einen amortisierten Zugriff von O(log n).

2
Alex

Lösung für den Fall, dass zwei Listen die gleichen Elemente, aber unterschiedliche Reihenfolge haben:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}
2
Pavlo Zvarych

Zusätzlich zu Laurence's Antwort, wenn Sie es auch null-sicher machen wollen:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}
1
Felixuko

Beispielcode:

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (sizeNewList == -1)) {
        return false;
    }

    if (sizeNewList != sizePrevoisList) {
        return true;
    }

    List n_prevois = new ArrayList(previousList);
    List n_new = new ArrayList(newList);

    try {
        Collections.sort(n_prevois);
        Collections.sort(n_new);
    } catch (ClassCastException exp) {
        return true;
    }

    for (int i = 0; i < sizeNewList; i++) {
        Object obj_prevois = n_prevois.get(i);
        Object obj_new = n_new.get(i);
        if (obj_new.equals(obj_prevois)) {
            // Object are same
        } else {
            return true;
        }
    }

    return false;
}
1
Jaydip Halake

Die equals-Methode von List erledigt dies, Listen sind geordnet. Um gleich zu sein, müssen zwei Listen die gleichen Elemente in derselben Reihenfolge haben.

return list1.equals(list2);
1
daveb
list1.equals(list2);

Wenn Ihre Liste eine benutzerdefinierte Klasse MyClass enthält, muss diese Klasse die Funktion equals überschreiben.

 class MyClass
  {
  int field=0;
  @0verride
  public boolean equals(Object other)
        {
        if(this==other) return true;
        if(other==null || !(other instanceof MyClass)) return false;
        return this.field== MyClass.class.cast(other).field;
        }
  }

Hinweis: Wenn Sie gleich auf Java.util.Set statt auf Java.util.List testen möchten, muss Ihr Objekt die hashCode-Funktion überschreiben.

1
Pierre

Sie können Apache's Bibliothek org.Apache.commons.collections verwenden: http://commons.Apache.org/collections/apidocs/org/Apache/commons/collections/ListUtils.html

public static boolean isEqualList(Java.util.Collection list1,
                              Java.util.Collection list2)
0
David Zhao

Überprüfen Sie, ob beide Listen keine Nullwerte sind. Wenn ihre Größe unterschiedlich ist, sind diese Listen nicht gleich. Erstellen Sie Karten, die aus den Elementen der Listen als Schlüssel und ihren Wiederholungen als Werten bestehen, und vergleichen Sie die Karten.

Annahmen, wenn beide Listen Nullen sind, halte ich sie für gleich.

private boolean compareLists(List<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(mapSize);

    for (Object o : list) {
        Integer count = map.get(o);
        if (count == null) {
            map.put(o, 1);
        } else {
            map.put(o, ++count);
        }
    }

    System.out.println(map);
    return map;
}

Bitte beachten Sie, dass die Methode equals für diese Objekte ordnungsgemäß definiert sein muss https://stackoverflow.com/a/24814634/4587961

0
Yan Khonski
0
Jeremy Smyth