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

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

IT小君 2021-12-09T03:34:39

我有一个家庭作业，我需要在ArrayList<Interger>以下条件下插入或添加新元素：

元素必须升序。
中没有重复的元素ArrayList<Integer>
插入方法运行O(n)次。

这是我在添加新元素之前检查重复元素的插入方法。

    public void insert(int x){
            //effect: Check duplicate elements if not x to the elements;
                boolean found = false;
                if(super.size()!=0){
                    for(int i=0; i<super.size(); i++){
                        if(super.get(i)==x){
                            found = true;
                        }
                    }
                }
                if(found){ return; }
                else{ super.add(x);  }
        }

我该怎么做？谢谢你。

添加

这是我的班级名称 InSetExtra

public class IntSetExtra extends ArrayList<Integer> {


    private static final long serialVersionUID = 1L;

    public IntSetExtra(){
        super();
    }

    public void insert(int x){
        //effect: Check duplicate elements if not x to the elements;
            boolean found = false;
            if(super.size()!=0){
                for(int i=0; i<super.size(); i++){
                    if(super.get(i)==x){
                        found = true;
                    }
                }
            }
            if(found){ return; }
            else{ super.add(x);  }
    }

    public String toString(){
        //effect: return string of this.
        if(super.size()==0) return "[]";
        String s = "[" + super.get(0).toString();
        for(int i=1; i<super.size(); i++){
            s += ", " + super.get(i).toString();
        }
        return s += "]";
    }

}

我需要插入大尺寸的元素，例如：

IntSetExtra a, b;

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

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

    System.out.println("a sub = "+a.toString().substring(0, 37));

我该怎么办？

附：我的导师只需要使用 ArrayList

点击广告，支持我们为你提供更好的服务

public void insert(int x){ // loop through all elements for (int i = 0; i < size(); i++) { // if the element you are looking at is smaller than x, // go to the next element if (get(i) < x) continue; // if the element equals x, return, because we don't add duplicates if (get(i) == x) return; // otherwise, we have found the location to add x add(i, x); return; } // we looked through all of the elements, and they were all // smaller than x, so we add ax to the end of the list add(x); }

public void insert(int x) { for (int i = 0; i < size(); i++) { if (x == get(i)) { // if new element is equal to current element do nothing and // return return; } else if (x > get(i)) { // if new element is greater than current element traverse to // next. continue; } // code reaches here if new element is smaller than current element // add element at this index and return. add(i, x); return; } // if end of list is reached while traversing then add new element and // return. (This will add element at the end of list) add(x); }

IT小君

这是我的方法：（评论中的解释）

您发布的当前解决方案看起来基本正确，除了它不会按升序保存元素的事实。

2021-12-09T03:34:40 回复

由于这是作业，我假设您必须使用 anArrayList并手动实现逻辑（而不是TreeSet用作明显的解决方案）。我认为以下提示应该足以让您完成实施:-)

如果数组元素已经按升序排列，则无需遍历整个数组。只需搜索等于或大于新元素的第一个元素。如果相等，你就被骗了。如果更大，在它之前插入新元素，你就完成了。如果所有现有元素都小于新元素，则将其插入到末尾。

这将为您提供 O(n) 所需的性能。但是，作为改进，您可以考虑使用二分搜索而不是linear。

为新数据结构创建一个类。

每当添加数据值时，对数组列表执行二分搜索以确保数据值不存在。如果它已经存在，则引发异常。如果它不存在，请将其插入到其排序位置。

在您的作业中记下，有一个现有的数据结构 (TreeSet) 可以执行此功能，但通过比您刚刚创建的更好的实现来实现。

~~为什么不使用 TreeSet：http : //download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html~~

由于这是 HomeWork 问题并且需要使用 ArrayList，因此我正在更改我的答案。

您将需要线性使用遍历并比较元素。采取相应措施：

如果新元素等于当前元素，则什么都不做并返回。
如果新元素大于当前元素，则遍历到下一个。
如果新元素小于当前元素，则在此索引处添加元素并返回。
如果遍历时到达列表末尾，则添加新元素并返回。（这将在列表末尾添加元素）

我在这里假设所有元素都是使用上述算法添加的。所以 ArrayList 总是排序的:)。

这是代码：

希望这可以帮助。

2021-12-09T03:34:41 回复

一个列表是一个列表而不是一个集合，如果它表现得像一个集合，它就违反了它的契约。在 TreeSet 中插入应该是 O(log(n)) 左右......