Вставить элемент в ArrayList с восходящим порядком и без дубликатов элементов

У меня есть домашнее задание, где мне нужно вставить или добавить новый элемент в 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

Ответы

Ответ 1

Вот как я это сделаю: (Объяснение в комментариях)

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

Текущее решение, которое вы разместили, выглядит в основном правильным, за исключением того, что оно не будет сохранять элементы в порядке возрастания.

Ответ 2

Вот способ вставки в O (n).

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

Ответ 3

Поскольку это домашнее задание, я предполагаю, что вы должны использовать ArrayList и реализовать логику вручную (вместо использования TreeSet в качестве очевидного решения). Я думаю, что для вас будет достаточно намека на завершение реализации: -)

Если элементы массива уже в порядке возрастания, вам не нужно перебирать весь массив. Просто найдите первый элемент, который равен или больше, чем новый элемент. Если вы равны, у вас есть обман. Если больше, вставьте новый элемент перед этим, и все будет готово. Если все существующие элементы меньше нового, вставьте его в конец.

Это даст вам O (n) производительность по мере необходимости. Однако в качестве улучшения вы можете использовать двоичный поиск вместо linear.

Ответ 4

~~Почему бы вам не использовать TreeSet: http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html~~

Поскольку это вопрос HomeWork и ArrayList нужно использовать, я меняю свой ответ.

Вам нужно будет использовать линейный ход и сравнить элементы. Примите меры:

если новый элемент равен текущему элементу, ничего не делать и возвращать.
если новый элемент больше текущего перемещения элемента к следующему.
если новый элемент меньше текущего элемента, добавьте элемент в этот индекс и верните.
если конец списка достигнут при прохождении, добавьте новый элемент и верните его. (Это добавит элемент в конце списка)

Я предполагаю, что все элементы добавляются с использованием вышеописанного алгоритма. Поэтому ArrayList всегда сортируется:).

вот код:

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

Надеюсь, что это поможет.

Ответ 5

Создайте класс для новой структуры данных.

Когда добавляется значение данных, выполните двоичный поиск в arraylist, чтобы убедиться, что значение данных еще не присутствует. Если он уже присутствует, вызовите исключение. Если его нет, вставьте его в свое отсортированное положение.

Запишите в своей домашней работе, что существует существующая структура данных (TreeSet), которая выполняет эту функцию, но делает это через лучшую реализацию, чем та, которую вы только что создали.

Ответ 6

Я использую TreeSet, когда хочу добавить недвойственные элементы в Set. Дайте ему шанс!

Ответ 7

Список - это список, а не набор, и если он ведет себя как набор, он нарушает его контракт. Вставка в TreeSet должна быть O (log (n)) или так...