Intersection et union des ArrayLists en Java

Existe-il des méthodes pour le faire? J'étais à la recherche, mais ne pouvais pas trouver toutes.

Une autre question: j'ai besoin de ces méthodes pour pouvoir filtrer les fichiers. Certains sont des filtres AND et d'autres sont des filtres OR (comme dans la théorie des ensembles), donc j'ai besoin de filtrer en fonction de tous les fichiers et des ArrayLists unite/intersects qui contiennent ces fichiers.

Dois-je utiliser une structure de données différente pour contenir les fichiers? Y at-il autre chose qui offrirait un meilleur temps d'exécution?

111
demandé sur informatik01 2011-03-12 17:21:27

19 réponses

Voici une implémentation simple sans utiliser de bibliothèque tierce. Principal avantage sur retainAll, removeAll et addAll est que ces méthodes ne modifient pas les listes d'origine entrées dans les méthodes.

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(t)) {
                list.add(t);
            }
        }

        return list;
    }
}
107
répondu adarshr 2011-03-12 14:50:14

Collection (donc ArrayList aussi) ont:

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

Utilisez une implémentation de liste si vous acceptez les répétitions, une implémentation de Set si vous ne le faites pas:

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]
110
répondu smas 2012-12-01 13:06:45

Ce post est assez vieux, mais néanmoins c'était le premier à apparaître sur google lors de la recherche de ce sujet.

Je veux donner une mise à jour en utilisant les flux Java 8 en faisant (fondamentalement) la même chose en une seule ligne:

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

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

Si quelqu'un a une solution meilleure/plus rapide, faites-le moi savoir, mais cette solution est une bonne doublure qui peut être facilement incluse dans une méthode sans ajouter une classe/méthode d'aide inutile et garder la lisibilité.

49
répondu Fat_FS 2018-04-27 01:39:54
list1.retainAll(list2) - is intersection

Union removeAll, puis addAll.

Trouver plus dans la documentation de collection (ArrayList est une collection) http://download.oracle.com/javase/1.5.0/docs/api/java/util/Collection.html

33
répondu The GiG 2016-11-01 08:01:48

Unions et intersections définies uniquement pour les ensembles, pas pour les listes. Comme vous l'avez mentionné.

Vérifiez la bibliothèqueguava pour les filtres. La goyave fournit également des intersections et des unions réelles

 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)
16
répondu Stan Kurilin 2016-08-04 11:45:53

Vous pouvez utiliser CollectionUtils depuis Apache commons .

10
répondu bluefoot 2013-05-03 14:27:30

La solution marquée n'est pas efficace. Il a une complexité temporelle O(N^2). Ce que nous pouvons faire est de trier les deux listes, et l'exécution d'un algorithme d'intersection comme celui ci-dessous.

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; 
}

Celui-ci a une complexité de O(N log n + n) Qui est dans O(N log n). L'union se fait de la même manière. Assurez-vous de faire les modifications appropriées sur l'if-elseif-else.

Vous pouvez également utiliser des itérateurs si vous le souhaitez (je sais qu'ils sont plus efficaces en C++, Je ne sais pas si cela est vrai en Java ainsi).

8
répondu AJed 2015-05-03 16:41:34

, je pense que vous devriez utiliser un Set pour contenir les fichiers si vous voulez faire de l'intersection et l'union sur eux. Ensuite, vous pouvez utiliser la classeGuava définit à faire union, intersection et filtrer par un Predicate aussi. La différence entre ces méthodes et les autres suggestions est que toutes ces méthodes créent des vues paresseuses de l'union, de l'intersection, etc. des deux ensembles. Apache Commons crée une nouvelle collection et y copie des données. retainAll modifie une de vos collections par la suppression des éléments.

4
répondu ColinD 2011-03-12 14:30:07

Voici un moyen de faire une intersection avec des flux (rappelez-vous que vous devez utiliser java 8 pour les flux):

List<foo> fooList1 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<foo> fooList2 = new ArrayList<>(Arrays.asList(new foo(), new foo()));
fooList1.stream().filter(f -> fooList2.contains(f)).collect(Collectors.toList());

Un exemple pour les listes avec différents types. Si vous avez une realtion entre foo et bar et que vous pouvez obtenir un bar-object de foo, vous pouvez modifier votre flux:

List<foo> fooList = new ArrayList<>(Arrays.asList(new foo(), new foo()));
List<bar> barList = new ArrayList<>(Arrays.asList(new bar(), new bar()));

fooList.stream().filter(f -> barList.contains(f.getBar()).collect(Collectors.toList());
4
répondu Deutro 2014-09-11 15:12:59
  • retainAll modifiera votre liste
  • Guava n'a pas D'API pour List (uniquement pour set)

J'ai trouvé ListUtils très utile pour ce cas d'utilisation.

Utilisez ListUtils depuis org.Apache.commun.collections si vous ne souhaitez pas modifier la liste existante.

ListUtils.intersection(list1, list2)

3
répondu Bala 2014-09-22 08:27:25

En Java 8, j'utilise des méthodes d'aide simples comme ceci:

public static <T> Collection<T> getIntersection(Collection<T> coll1, Collection<T> coll2){
    return Stream.concat(coll1.stream(), coll2.stream())
            .filter(coll1::contains)
            .filter(coll2::contains)
            .collect(Collectors.toSet());
}

public static <T> Collection<T> getMinus(Collection<T> coll1, Collection<T> coll2){
    return coll1.stream().filter(not(coll2::contains)).collect(Collectors.toSet());
}

public static <T> Predicate<T> not(Predicate<T> t) {
    return t.negate();
}
2
répondu Pascalius 2018-02-06 11:11:12

Si les objets de la liste sont hashable (c'est-à-dire ont un hashCode décent et une fonction égale), l'approche la plus rapide entre les tables env. taille > 20 est de construire un HashSet pour la plus grande des deux listes.

public static <T> ArrayList<T> intersection(Collection<T> a, Collection<T> b) {
    if (b.size() > a.size()) {
        return intersection(b, a);
    } else {
        if (b.size() > 20 && !(a instanceof HashSet)) {
            a = new HashSet(a);
        }
        ArrayList<T> result = new ArrayList();
        for (T objb : b) {
            if (a.contains(objb)) {
                result.add(objb);
            }
        }
        return result;
    }
}
1
répondu Jeroen Vuurens 2015-04-12 07:48:19

Je travaillais aussi sur la situation similaire et je suis arrivé ici à la recherche d'aide. Fini par trouver ma propre solution pour les Tableaux. ArrayList AbsentDates = new ArrayList (); / / stockera Array1-Array2

Remarque: poster ceci si cela peut aider quelqu'un à atteindre cette page pour obtenir de l'aide.

ArrayList<String> AbsentDates = new ArrayList<String>();//This Array will store difference
      public void AbsentDays() {
            findDates("April", "2017");//Array one with dates in Month April 2017
            findPresentDays();//Array two carrying some dates which are subset of Dates in Month April 2017

            for (int i = 0; i < Dates.size(); i++) {

                for (int j = 0; j < PresentDates.size(); j++) {

                    if (Dates.get(i).equals(PresentDates.get(j))) {

                        Dates.remove(i);
                    }               

                }              
                AbsentDates = Dates;   
            }
            System.out.println(AbsentDates );
        }
1
répondu Shubham Pandey 2017-04-17 04:50:47

Vous pouvez utiliser des communes-collections4 CollectionUtils

Collection<Integer> collection1 = Arrays.asList(1, 2, 4, 5, 7, 8);
Collection<Integer> collection2 = Arrays.asList(2, 3, 4, 6, 8);

Collection<Integer> intersection = CollectionUtils.intersection(collection1, collection2);
System.out.println(intersection); // [2, 4, 8]

Collection<Integer> union = CollectionUtils.union(collection1, collection2);
System.out.println(union); // [1, 2, 3, 4, 5, 6, 7, 8]

Collection<Integer> subtract = CollectionUtils.subtract(collection1, collection2);
System.out.println(subtract); // [1, 5, 7]
1
répondu xxg 2017-12-09 15:07:06

Solution Finale:

//all sorted items from both
public <T> List<T> getListReunion(List<T> list1, List<T> list2) {
    Set<T> set = new HashSet<T>();
    set.addAll(list1);
    set.addAll(list2);
    return new ArrayList<T>(set);
}

//common items from both
public <T> List<T> getListIntersection(List<T> list1, List<T> list2) {
    list1.retainAll(list2);
    return list1;
}

//common items from list1 not present in list2
public <T> List<T> getListDifference(List<T> list1, List<T> list2) {
    list1.removeAll(list2);
    return list1;
}
0
répondu Choletski 2016-09-26 12:36:00

Tout d'abord, je copie toutes les valeurs des tableaux dans un seul tableau, puis je supprime les valeurs de doublons dans le tableau. Ligne 12, expliquant si le même nombre se produit plus de temps, puis mettre une valeur de poubelle supplémentaire en position "j". À la fin, traversez à partir de start-end et vérifiez si la même valeur de mémoire se produit, puis jetez.

public class Union {
public static void main(String[] args){

    int arr1[]={1,3,3,2,4,2,3,3,5,2,1,99};
    int arr2[]={1,3,2,1,3,2,4,6,3,4};
    int arr3[]=new int[arr1.length+arr2.length];

    for(int i=0;i<arr1.length;i++)
        arr3[i]=arr1[i];

    for(int i=0;i<arr2.length;i++)
        arr3[arr1.length+i]=arr2[i];
    System.out.println(Arrays.toString(arr3));

    for(int i=0;i<arr3.length;i++)
    {
        for(int j=i+1;j<arr3.length;j++)
        {
            if(arr3[i]==arr3[j])
                arr3[j]=99999999;          //line  12
        }
    }
    for(int i=0;i<arr3.length;i++)
    {
        if(arr3[i]!=99999999)
            System.out.print(arr3[i]+" ");
    }
}   
}
0
répondu Ashutosh 2017-06-14 15:49:22

Après le test, voici ma meilleure approche d'intersection.

Vitesse plus rapide par rapport à L'approche pure HashSet. HashSet et HashMap ci-dessous ont des performances similaires pour les tableaux avec plus de 1 million d'enregistrements.

Comme pour L'approche de flux Java 8, la vitesse est assez lente pour une taille de tableau plus grande que 10k.

J'Espère que cela peut aider.

public static List<String> hashMapIntersection(List<String> target, List<String> support) {
    List<String> r = new ArrayList<String>();
    Map<String, Integer> map = new HashMap<String, Integer>();
    for (String s : support) {
        map.put(s, 0);
    }
    for (String s : target) {
        if (map.containsKey(s)) {
            r.add(s);
        }
    }
    return r;
}
public static List<String> hashSetIntersection(List<String> a, List<String> b) {
    Long start = System.currentTimeMillis();

    List<String> r = new ArrayList<String>();
    Set<String> set = new HashSet<String>(b);

    for (String s : a) {
        if (set.contains(s)) {
            r.add(s);
        }
    }
    print("intersection:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
    return r;
}

public static void union(List<String> a, List<String> b) {
    Long start = System.currentTimeMillis();
    Set<String> r= new HashSet<String>(a);
    r.addAll(b);
    print("union:" + r.size() + "-" + String.valueOf(System.currentTimeMillis() - start));
}
0
répondu Dilabeing 2018-09-18 03:19:59

Si vous aviez vos données dans des ensembles, vous pouvez utiliser les goyaves Sets classe.

-1
répondu Neil 2016-10-26 06:15:36

Si le nombre correspond à ce que je vérifie, il se produit la première fois ou non avec l'aide de "indexOf()" si le nombre correspond à la première fois, puis imprimez et enregistrez dans une chaîne de sorte que lorsque la prochaine fois le même nombre correspond, il ne sera pas imprimé car en raison de la condition "indexOf()" sera false.

class Intersection
{
public static void main(String[] args)
 {
  String s="";
    int[] array1 = {1, 2, 5, 5, 8, 9, 7,2,3512451,4,4,5 ,10};
    int[] array2 = {1, 0, 6, 15, 6, 5,4, 1,7, 0,5,4,5,2,3,8,5,3512451};


       for (int i = 0; i < array1.length; i++)
       {
           for (int j = 0; j < array2.length; j++)
           {
               char c=(char)(array1[i]);
               if(array1[i] == (array2[j])&&s.indexOf(c)==-1)
               {    
                System.out.println("Common element is : "+(array1[i]));
                s+=c;
                }
           }
       }    
}

}

-1
répondu Ashutosh 2017-06-14 15:37:46