Union, Intersection, grande différence IntSet en O (m + n) fois

Question

De ma question

Insert element to ArrayList with ascending order and no duplicate elements

Je l'ai fait ma méthode d'insertion.

Maintenant, j'essaie de savoir comment construire union, intersection et méthodes de différence pour faire fonctionner 2 IntSets.

Notez que les éléments de nombre d'IntSet sont grands et que je dois le faire en O (m + n) où m et n sont le nombre d'éléments des deux IntSet.

Par exemple, IntSets

a = new IntSetExtra(); 
b = new IntSetExtra(); 

for(int i=0; i<300; i++){ a.insert(2*i); } 
for(int i=0; i<300; i++){ a.insert(i); } 

for(int i=20000; i<50000; i++){ b.insert(i); } 

Comment puis-je faire?

P.S. il peut utiliser mergesort?

modifier:

Voici mon code union

public IntSetExtra union(IntSetExtra a){ 
    //effect: return new IntSet that union between this and a; 
    IntSetExtra intSet = new IntSetExtra(); 
    intSet.addAll(a); 
    for(int i=0; i<a.size(); i++){ 
     if(!intSet.contains(a.get(i))){ 
      intSet.insert(a.get(i)); 
     } 
    } 
    return intSet; 
} 

Answer 1

Vous pouvez simplement utiliser les méthodes des collections Java telles que addAll(Collection), removeAll(Collection) et retainAll(Collection).

Par exemple, l'intersection de deux ensembles:

public Set<V> intersection(Set<? extends V> a, Set<? extends V> b) { 
    // you may swap a and b, so a would contain the smaller collection 
    Set<V> result = new HashSet<V>(a); 
    result.retainAll(b); 
    return result; 
}