Объединение, пересечение, большая разница IntSet в O (m + n) раз

Question

Объединение, пересечение, большая разница IntSet в O (m + n) раз

Из моего вопроса

Вставить элемент в ArrayList в порядке возрастания и без повторяющихся элементов

Я выполнил свой метод вставки.

Теперь я пытаюсь выяснить, как построить методы объединения, пересечения и разности для работы с двумя объектами IntSet.

Обратите внимание, что количество элементов IntSet велико, и мне нужно сделать это за O (m + n) раз, где m и n - количество элементов двух IntSet.

Например 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); }

Как это сделать?

P.S. он может использовать сортировку слиянием?

редактировать:

Вот мой код объединения

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

1

java set-difference set-intersection set-operations set-union

задан Community 23 May 2017 в 11:54

1 ответ

Другие вопросы по тегам:

java set-difference set-intersection set-operations set-union

Похожие вопросы:

score 2 · Answer 1

Вы можете просто использовать методы коллекций Java, такие как addAll(Collection), removeAll(Collection) и retainAll(Collection) .

Например, пересечение двух наборов:

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