O(m+n) 次的并、交、差大 IntSet

发布于 2024-09-16 09:38:06 字数 988 浏览 2 评论 0原文

从我的问题

以升序将元素插入到 ArrayList并且没有重复的元素

我已经完成了插入方法。

现在我尝试找出如何构建并集、交集和差集方法来对 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); }

我该怎么做？

PS它可以使用归并排序吗？

编辑：

这是我的工会代码

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

原文

From my question

Insert element to ArrayList with ascending order and no duplicate elements

I've done my insert method.

Now I try to find out how to build union, intersection, and difference methods to operate on 2 IntSets.

Notice that the number elements of IntSet is large and I need to do it in O(m+n) time where m and n are the number of elements of the two IntSets.

For example 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); }

How can I do it?

P.S. it can use mergesort?

edit:

Here is my union code

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

原谅过去的我 2024-09-23 09:38:06

您可以只使用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;
}

You may just use the methods of java collections such as addAll(Collection), removeAll(Collection) and retainAll(Collection).

For example, the intersection of two sets:

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

回复收藏 0 原文

~没有更多了~