聯盟，相交，爲O差異大INTSET（M + N）次

Question

從我的問題

Insert element to ArrayList with ascending order and no duplicate elements

我做我的插入方法。

現在我試着找出如何構建聯合，相交和差分方法來操作2個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.它可以使用mergesort？

編輯：

這裏是我的組織機構代碼

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

你可能只需要使用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; 
}