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

Question

У меня есть домашнее задание, где мне нужно вставить или добавить новый элемент в ArrayList<Interger> с следующим условием:

1. Элемент должен по возрастанию .

2. Нет дубликатов элементов в ArrayList<Integer>

3. метод вставки выполняется в 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

Answer 1

Вот метод вставки в O (n).

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

Почему бы вам не использовать 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);
}

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

Answer 6

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

Answer 7

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