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

Question

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

1. элементом должен порядка возрастания. не

2. Нет повторяющихся элементов в методе ArrayList<Integer>

3. вставки в перспективе O (п) раз.

Вот мой метод вставки для проверки дублирующего элемента перед добавлением нового элемента.

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

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

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 2

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

Answer 3

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

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

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

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

Надеется, что это помогает.

Answer 5

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

Answer 6

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

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

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

Answer 7

Ниже приведен метод вставки в O (n).

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