联盟，相交，为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; 
}