Вставить элемент в ArrayList в порядке возрастания и без повторяющихся элементов
У меня есть домашнее задание, где мне нужно вставить или добавить новый элемент в ArrayList с следующим условием:
Элемент должен возрастать order .
Нет повторяющихся элементов в
ArrayListметод вставки запущен в 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
6 ответов
Вот метод вставки за O(n).
public void insert(int x) {
int pos = Collections.binarySearch(this, x);
if (pos < 0) {
add(-pos-1, x);
}
}
Создайте класс для новой структуры данных.
Всякий раз, когда добавляется значение данных, выполняйте двоичный поиск в списке массивов, чтобы убедиться, что значение данных еще не присутствует. Если он уже присутствует, создайте исключение. Если его нет, вставьте его в отсортированное положение.
Отметьте в домашнем задании, что существует существующая структура данных (TreeSet), которая выполняет эту функцию, но делает это с помощью лучшей реализации, чем та, которую вы только что создали.
Почему бы вам не использовать 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);
}
Надеюсь, это поможет.
Я использую TreeSet, когда хочу добавить в набор неповторяющиеся элементы. Дать ему шанс!
Список — это список, а не набор, и если он ведет себя как набор, он нарушает свой контракт. Вставка в TreeSet должна быть O(log(n)) или около того...
Поскольку это домашнее задание, я предполагаю, что вы должны использовать ArrayList и реализовывать логику вручную (а не использовать TreeSet как очевидное решение). Я думаю, что следующей подсказки должно быть достаточно, чтобы завершить реализацию :-)
Если элементы массива уже расположены в порядке возрастания, вам не нужно перебирать весь массив в цикле. Просто найдите первый элемент, который равен или больше нового элемента. Если равны, у вас есть обман. Если больше, вставьте новый элемент перед ним, и все готово. Если все существующие элементы меньше нового, вставьте его в конец.
Это даст вам требуемую производительность O(n). Однако в качестве улучшения вы можете рассмотреть возможность использования бинарного поиска вместо линейного.