Блог

Главная - Вопросы по программированию - У меня возникли проблемы с добавлением элемента в уже упорядоченный по алфавиту массив

У меня возникли проблемы с добавлением элемента в уже упорядоченный по алфавиту массив

#java #arrays

#java #массивы

Вопрос:

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

Любая помощь или толчок в правильном направлении были бы оценены. Спасибо!

Метод должен следовать этим инструкциям:

      - Adds an item to the list.  This method assumes that the list is already
      sorted in alphabetical order based on the names of the items in the list.

     - The new item will be inserted into the list in the appropriate place so
      that the list will remain alphabetized by names.

      In order to accommodate the new item, the internal array must be re-sized 
      so that it is one unit larger than it was before the call to this method.


public void add(Listable itemToAdd) {
         Listable[] items1;
         int newlength = items.length 1;
         items1 = new Listable [newlength];
         for(int i = 0;i<items.length;i  ){
             items1[i] = items[i];
             items1[newlength-1] = itemToAdd;
         }
    }

Комментарии:

1. Возможно, это ленивый способ сделать это, но почему бы не добавить его в конец и повторно отсортировать? Звучит как вопрос домашнего задания 🙂

2. И, конечно, есть подход AVL tree. Также не уверен, что это лучшее решение.

3. Вы присваиваете itemToAdd последнему элементу массива при каждом цикле. Поскольку массив уже отсортирован, можете ли вы придумать способ найти, куда элемент следует добавить в массив?

Ответ №1:

Это неплохо для начала! Нам нужно сделать ряд вещей. Эта строка

 items1[newlength-1] = itemToAdd;

необходимо выйти из цикла и быть размещенным впоследствии — вы будете присваивать какому-либо элементу массива это значение только один раз, да, и не много раз?

Копирование — хорошее начало. Что вам нужно сделать, это

  1. Найдите местоположение, куда должен помещаться новый элемент (выполните поиск по массиву и найдите элемент, после которого должен располагаться новый)
  2. Скопируйте элементы, которые идут перед новым элементом
  3. Скопируйте новый элемент
  4. Скопируйте элементы, которые идут после нового элемента (корректируя их индексы, поскольку все они на единицу позже, чем раньше!)

Имеет смысл?

Комментарии:

1. В том-то и дело, что в массиве нет указанного списка элементов, поэтому я бы точно не знал, куда он ведет.

2. Если я вас не неправильно понял, есть лучший (и более простой) способ сделать это.

3. @Sathish: Вам нужно провести сравнения, чтобы выяснить, куда должен идти элемент. Например, сравните имена двух элементов, используя compareTo метод.

4. Итак, как бы мне реализовать метод compareTo, чтобы определить, где параметр поместится в массиве?

5. String уже есть собственный подходящий compareTo() метод.

Ответ №2:

Если вы посещаете курс для начинающих, возможно, вы узнали о сортировке по вставке. Одним из интересных свойств сортировки по вставке является то, что, несмотря на плохое время выполнения в среднем случае (O (n2)), его производительность в лучшем случае (отсортированный список) довольно хорошая — O (n), на самом деле. Почти отсортированный список будет выполняться в том же классе эффективности. Это может быть способом выполнить то, что вы пытаетесь сделать. (Это также может быть одно из немногих мест, где вы когда-либо будете использовать сортировку по вставке, так что используйте это по максимуму.)