插入元素与按升序排列，没有重复的元素ArrayList的 [英] Insert element to ArrayList with ascending order and no duplicate elements

问题描述

我有一个家庭作业，我需要插入或添加新的elemment到的ArrayList＆LT;基于整数＆GT; 与如下条件：

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

1. 元素必须升序排列

否重复在元素的ArrayList＆LT;整数GT;

insert方法中的 O（N）次运行。

insert method run in O(n) times.

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

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.

除了

这是我的类名InSetExtra

here is my class names 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));

我应该怎么办？

PS。我的导师只需要使用的ArrayList

ps. my instructor need to use only ArrayList

推荐答案

下面是我会怎么做：（注释中说明）

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.

这篇关于插入元素与按升序排列，没有重复的元素ArrayList的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！