Schnittmenge und Vereinigung von ArrayLists in Java

Lesezeit: 7 Minuten

Schnittmenge und Vereinigung von ArrayLists in Java
Yotamoo

Gibt es Methoden dafür? Ich habe gesucht, aber keine gefunden.

Eine andere Frage: Ich brauche diese Methoden, damit ich Dateien filtern kann. Einige sind AND Filter und einige sind OR Filter (wie in der Mengenlehre), also muss ich nach allen Dateien und den unite/intersects ArrayLists filtern, die diese Dateien enthalten.

Sollte ich eine andere Datenstruktur verwenden, um die Dateien zu speichern? Gibt es etwas anderes, das eine bessere Laufzeit bieten würde?

  • Wenn Sie keine neue Liste erstellen möchten, schneidet Vector.retainAll(Vector) Ihren ursprünglichen Vektor nur auf den Schnittpunkt mit dem zweiten Vektor.

    – Benutzer2808054

    16. Januar 2015 um 17:50 Uhr

  • @ user2808054 warum Vector? Von dieser Klasse wird seit Java 1.2 abgeraten.

    – dimo414

    26. Oktober 2016 um 6:25 Uhr

  • @ dimo414 eine Schnittstelle, die ich verwende (ich habe keine Option), gibt Dinge als Vektoren zurück. Ich wusste nicht, dass es entmutigt worden war! Danke für die Info .. Von wem entmutigt ? Ich habe keinen Hinweis darauf gesehen, dass es veraltet ist, daher ist dies eine Überraschung

    – Benutzer2808054

    1. November 2016 um 18:02 Uhr


  • Aus den Javadocs: “Ab der Java 2-Plattform v1.2 … wird empfohlen, ArrayList anstelle von Vector zu verwenden.“. Das einzige Mal, dass Sie könnte brauchen Vector ist für Thread-übergreifende Interaktionen, aber auch für diese Anwendungsfälle gibt es sicherere Datenstrukturen. Siehe auch diese Frage. Jede Bibliothek, die noch verwendet wird Vector im Jahr 2016 ist meiner Meinung nach sehr verdächtig.

    – dimo414

    1. November 2016 um 20:27 Uhr

  • @ dimo414 es ist eine IBM-Bibliothek, haha! (Lotus Domino-Daten-API). Danke für die Info, sehr hilfreich

    – Benutzer2808054

    8. November 2016 um 16:09 Uhr

1646266631 993 Schnittmenge und Vereinigung von ArrayLists in Java
adarshr

Hier ist eine einfache Implementierung ohne Verwendung einer Bibliothek von Drittanbietern. Hauptvorteil gegenüber retainAll, removeAll und addAll ist, dass diese Methoden die ursprüngliche Listeneingabe in die Methoden nicht ändern.

public class Test {

    public static void main(String... args) throws Exception {

        List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
        List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

        System.out.println(new Test().intersection(list1, list2));
        System.out.println(new Test().union(list1, list2));
    }

    public <T> List<T> union(List<T> list1, List<T> list2) {
        Set<T> set = new HashSet<T>();

        set.addAll(list1);
        set.addAll(list2);

        return new ArrayList<T>(set);
    }

    public <T> List<T> intersection(List<T> list1, List<T> list2) {
        List<T> list = new ArrayList<T>();

        for (T t : list1) {
            if(list2.contains
                list.add
            }
        }

        return list;
    }
}

  • Sie können eine neue Liste mit list1-Elementen erstellen und dann die Methoden “retainAll” und “addAll” aufrufen

    – Lukastymo

    12. März 2011 um 14:44 Uhr

  • Warum verwenden Sie in dieser Lösung strictfp?

    – Lukastymo

    12. März 2011 um 14:47 Uhr

  • Sollte a verwenden HashSet zum intersection sodass die durchschnittliche Fallleistung O(n) statt O(n^2) ist.

    – Zong

    16. März 2015 um 23:30 Uhr

  • Dieser Beitrag könnte ein Update gebrauchen, um die Vorteile der Java 8 Stream API zu demonstrieren.

    – KMU_Entw

    2. September 2015 um 15:57 Uhr

  • Ich erhalte eine Fehlermeldung, wenn ich versuche, diesen Wert zuzuweisen -> Beispiel: ArrayList total total = (ArrayList) Schnittpunkt (list2, list1) —>kann java.util.arraylist nicht in java.util.arraylist umwandeln< Zeichenfolge>

    Benutzer3402040

    11. Februar 2016 um 9:34 Uhr


Schnittmenge und Vereinigung von ArrayLists in Java
Lukastymo

Sammlung (also auch ArrayList) haben:

col.retainAll(otherCol) // for intersection
col.addAll(otherCol) // for union

Verwenden Sie eine List-Implementierung, wenn Sie Wiederholungen akzeptieren, eine Set-Implementierung, wenn Sie dies nicht tun:

Collection<String> col1 = new ArrayList<String>(); // {a, b, c}
// Collection<String> col1 = new TreeSet<String>();
col1.add("a");
col1.add("b");
col1.add("c");

Collection<String> col2 = new ArrayList<String>(); // {b, c, d, e}
// Collection<String> col2 = new TreeSet<String>();
col2.add("b");
col2.add("c");
col2.add("d");
col2.add("e");

col1.addAll(col2);
System.out.println(col1); 
//output for ArrayList: [a, b, c, b, c, d, e]
//output for TreeSet: [a, b, c, d, e]

  • Es gab einen Änderungsvorschlag für diese Vereinigung “ist falsch, da es gemeinsame Elemente zweimal enthalten wird”. Die Bearbeitung empfahl die Verwendung von a HashSet stattdessen.

    – Kos

    30. November 2012 um 17:26 Uhr

  • Tatsächlich wurde es bearbeitet, siehe: “Verwenden Sie eine List-Implementierung, wenn Sie Wiederholungen akzeptieren, eine Set-Implementierung, wenn Sie dies nicht tun:”

    – Lukastymo

    12. September 2013 um 10:53 Uhr

  • Nein, “retainAll” ist kein Schnittpunkt für “list”. Oben werden alle Elemente in col entfernt, die sich nicht in otherCol befinden. Nehmen wir an, otherCol ist {a,b,b,c} und col ist {b,b,b,c,d}. Dann endet col mit {b,b,b,c}, was nicht unbedingt der Schnittpunkt der beiden ist. Ich würde erwarten, dass das {b,b,c} ist. Es wird eine andere Operation durchgeführt.

    – Dämongolem

    18. März 2016 um 18:02 Uhr

  • Ich sehe auch nicht wie addAll() ist Union für Listen; es wird nur die zweite Liste mit dem Ende der ersten verkettet. Eine Vereinigungsoperation würde das Hinzufügen eines Elements vermeiden, wenn die erste Liste es bereits enthält.

    – dimo414

    26. Oktober 2016 um 6:23 Uhr

1646266632 120 Schnittmenge und Vereinigung von ArrayLists in Java
steilerDev

Dieser Beitrag ist ziemlich alt, aber trotzdem war er der erste, der bei der Suche nach diesem Thema bei Google auftauchte.

Ich möchte ein Update mit Java 8-Streams geben, das (im Grunde) dasselbe in einer einzigen Zeile macht:

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

List<T> union = Stream.concat(list1.stream(), list2.stream())
    .distinct()
    .collect(Collectors.toList());

Wenn jemand eine bessere/schnellere Lösung hat, lassen Sie es mich wissen, aber diese Lösung ist ein netter Einzeiler, der leicht in eine Methode aufgenommen werden kann, ohne eine unnötige Hilfsklasse/-methode hinzuzufügen, und trotzdem die Lesbarkeit beibehält.

  • Ooof, es könnte ein netter Einzeiler sein, aber es dauert O(n^2) Zeit. Wandeln Sie eine der Listen in a um Set dann benutze die Sets contains Methode. Nicht alles im Leben muss mit Streams erledigt werden.

    – dimo414

    26. Oktober 2016 um 6:22 Uhr

1646266632 45 Schnittmenge und Vereinigung von ArrayLists in Java
Die GiG

list1.retainAll(list2) - is intersection

Gewerkschaft wird removeAll und dann addAll.

Weitere Informationen finden Sie in der Dokumentation der Sammlung (ArrayList ist eine Sammlung)
http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html

Schnittmenge und Vereinigung von ArrayLists in Java
Stan Kurilin

Unions und Schnittmengen, die nur für Mengen definiert sind, nicht für Listen. Wie du erwähnt hast.

Überprüfen Guave Bibliothek für Filter. Auch Guave bietet echte Kreuzungen und Vereinigungen

 static <E> Sets.SetView<E >union(Set<? extends E> set1, Set<? extends E> set2)
 static <E> Sets.SetView<E> intersection(Set<E> set1, Set<?> set2)

1646266633 288 Schnittmenge und Vereinigung von ArrayLists in Java
tomrozb

Sie können verwenden CollectionUtils von Apache Commons.

Die markierte Lösung ist nicht effizient. Es hat eine Zeitkomplexität von O (n ^ 2). Was wir tun können, ist, beide Listen zu sortieren und einen Schnittpunktalgorithmus wie den folgenden auszuführen.

private  static ArrayList<Integer> interesect(ArrayList<Integer> f, ArrayList<Integer> s) { 
    ArrayList<Integer> res = new ArrayList<Integer>();

    int i = 0, j = 0; 
    while (i != f.size() && j != s.size()) { 

        if (f.get(i) < s.get(j)) {
            i ++;
        } else if (f.get(i) > s.get(j)) { 
            j ++;
        } else { 
            res.add(f.get(i)); 
            i ++;  j ++;
        }
    }


    return res; 
}

Dieser hat eine Komplexität von O(n log n + n), die in O(n log n) enthalten ist. Die Vereinigung erfolgt auf ähnliche Weise. Stellen Sie nur sicher, dass Sie die entsprechenden Änderungen an den if-elseif-else-Anweisungen vornehmen.

Sie können auch Iteratoren verwenden, wenn Sie möchten (ich weiß, dass sie in C ++ effizienter sind, ich weiß nicht, ob dies auch in Java gilt).

  • Nicht generisch genug, T ist möglicherweise nicht vergleichbar und in einigen Fällen ist Vergleichen teuer …

    – Boris Churzin

    19. Juni 2016 um 16:28 Uhr

  • Nicht generisch, ich stimme voll und ganz zu. Vergleich ist teuer? wie würdest du das lösen?

    – AJed

    19. Juni 2016 um 21:12 Uhr

  • Leider – es wäre billiger, es in O (n ^ 2) zu tun 🙂 Für Zahlen ist diese Lösung gut …

    – Boris Churzin

    21. Juni 2016 um 12:37 Uhr

  • Leider – Sie haben meine Frage nicht beantwortet. Lassen Sie es mich umformulieren, wie ist O (n ^ 2) besser, wenn eine Vergleichsfunktion der Kosten c (n) gegeben ist?

    – AJed

    22. Juni 2016 um 5:10 Uhr

  • Konvertieren einer Eingabe in eine Menge und Aufrufen contains() in einer Schleife (wie Devenv vorschlägt) würde O(n + m) Zeit in Anspruch nehmen. Das Sortieren ist unnötig kompliziert und benötigt O(n log n + m log n + n) Zeit. Zugegeben, das reduziert sich auf die Zeit O (n log n), aber das ist immer noch schlimmer als die lineare Zeit und viel komplexer.

    – dimo414

    26. Oktober 2016 um 6:36 Uhr

917630cookie-checkSchnittmenge und Vereinigung von ArrayLists in Java

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy