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

Insert element to ArrayList with ascending order and no duplicate elements

提问by Giffary

I have a homework assignment where I need to insert or add new elemment into ArrayList<Interger>with follow condition:

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

1. Element must ascending order.

2. No duplicateelements in ArrayList<Integer>

3. insert method run in O(n)times.

1. 元素必须升序。

2. 中没有重复的元素ArrayList<Integer>

3. 插入方法运行O(n)次。

Here is my insert method for check duplicate element before add new element.

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

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

how can i do it? Thank you.

我该怎么做？谢谢你。

addition

添加

here is my class names InSetExtra

这是我的班级名称 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 += "]";
    }

}

and i need to insert a large size of elements, for example:

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

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

what should i do?

我该怎么办？

ps. my instructor need to use only ArrayList

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

采纳答案by jjnguy

Here is how I would do it: (Explanation in comments)

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

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

The current solution that you posted looks mostly correct, except for the fact that it will not save elements in ascending order.

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

回答by DaHymanal

I use TreeSet when i want to add non-duplicate elements to a Set. Give it a shot!

当我想向 Set 添加非重复元素时，我使用 TreeSet。试一试！

回答by Péter T?r?k

Since this is homework, I assume you must use an ArrayListand implement the logic manually (rather than using TreeSetas the obvious solution). I think the following hint should be enough for you to finalize the implementation :-)

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

If the array elements are already in ascending order, you don't need to loop through the whole array. Just search for the first element which is equal to or greater than the new element. If equal, you have a dupe. If greater, insert the new element before it and you are done. If all existing elements are smaller than the new one, insert it at the end.

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

This will give you O(n) performance as required. However, as an improvement, you may consider using binary searchinstead of linear.

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

回答by YoK

Why don't you use TreeSet: http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html

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

As this is HomeWork question and ArrayList need to be used I am changing my answer.

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

You will need to use traverse linearly and compare elements. Take action accordingly:

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

• if new element is equal to current element do nothing and return.
• if new element is greater than current element traverse to next.
• if new element is smaller than current element add element at this index and return.
• if end of list is reached while traversing then add new element and return. (This will add element at the end of list)

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

I assume here that all elements are added using above algorithm. So ArrayList is always sorted :).

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

here is code:

这是代码：

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

Hope this helps.

希望这可以帮助。

回答by Landei

A list is a list and not a set, and if it behaves like a set, it breaks its contract. Inserting in a TreeSet should be O(log(n)) or so...

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

回答by babbitt

Create a class for the new data structure.

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

Whenever a data value is added, perform a binary search on the arraylist to ensure that the data value is not already present. If it is already present, raise an exception. If it is not present, insert it into its sorted position.

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

Make a note in your homework that there is an existing data structure (TreeSet) that performs this functionality, but does so via a better implementation than the one you just created.

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

回答by Maurice Perry

Here is an insert method in O(n).

这是 O(n) 中的插入方法。

public void insert(int x) {
    int pos = Collections.binarySearch(this, x);
    if (pos < 0) {
        add(-pos-1, x);
    }
}