#java #arraylist #comparator #comparable
#java #arraylist #компаратор #сопоставимый
Вопрос:
У меня есть пользовательский интерфейс ArrayList, который расширяет сопоставимый класс и находится в порядке возрастания. Класс, над которым я работаю, реализует этот интерфейс.
Моя проблема в том, что мне нужно отредактировать метод add, чтобы он добавлял элемент в ArrayList, оставлял список упорядоченным и следил за тем, чтобы дубликатов не было.
Было бы легко сделать все это отдельными методами, но об этом не может быть и речи. Мне нужен один метод для выполнения всего этого, чтобы при вызове метода (если он не является дубликатом) элемент добавлялся в правильном положении.
Кроме того, чтобы проверить положение индекса, в который нужно вставить метод, я должен использовать метод compareTo(), унаследованный от сопоставимого класса. Единственная проблема в том, что я должен реализовать свой собственный метод compareTo () в классе, над которым я работаю. Я просмотрел все, и я запутался в том, как это сделать для этого определенного класса.
Вот мой код на данный момент:
public void add(E item) throws IndexOutOfBoundsException {
if (contains(item)) {
throw new IllegalArgumentException("This is a duplicate!");
}
//here is where I need the implementation to add the item to the array, in order
}
Тогда вот мой метод compareTo():
public int compareTo(E item) {
if () {
return -1;
}
else if () {
return 1;
}
else {
return 0;
}
}
Комментарии:
1. У List есть метод contains(Object o), который выполняет то, что делает ваш цикл. Это упрощает код.
2. Подсказка: сортировка по вставке ( en.wikipedia.org/wiki/Insertion_sort )
3. Какую часть вы не понимаете? Мы не должны делать за вас домашнюю работу. 🙂 Вам придется ознакомиться с этим материалом во время экзамена.
4. использование == означает, что в списке есть один и тот же объект, а не то, что два объекта равны. используйте .equals(объект o). — или просто используйте contains(объект o)
5. 1) Я предполагаю, что у вас есть класс, расширяющий ArrayList. 2) какие элементы вы добавляете? как вы их сравниваете / сортируете?
Ответ №1:
Один из способов сделать это — сначала проверить, есть ли
myArrayList.contains(item)
а затем, если нет, просто вставьте и пересортируйте свой массив:
myArrayList.add(item);
Collections.sort(myArrayList);
Обратите внимание, что в общем случае, если вы хотите поддерживать отсортированный набор без дубликатов, существуют структуры данных получше, чем ArrayList .
Комментарии:
1. спасибо за ввод. я изменил проверку дубликатов, чтобы использовать метод contains(). На самом деле у меня это было раньше. единственная проблема в том, что мне нужен метод, чтобы сначала вставить его, а не сортировать. он должен оставаться отсортированным после вызова метода.
Ответ №2:
Как насчет набора деревьев? Похоже, что он имеет поведение, которое вы ищете.
Ответ №3:
Вы не предоставляете так много информации. Если вы действительно реализуете структуру данных, подобную ArrayList, то сначала вам нужно посмотреть, достаточно ли велик массив для добавления нового элемента. Если нет, вам нужно создать новый массив. В первом случае вам нужно найти местоположение для ввода нового элемента, переместить все с этой позиции на единицу вниз, а затем добавить элемент. Во втором случае вы можете «объединить» старый список с новым элементом (то есть продолжать добавлять из старого списка до тех пор, пока не появится местоположение, куда должен перейти новый элемент, добавьте новый элемент и продолжайте). У меня есть еще один вопрос: куда помещается compareTo (объект o)? Если вы добавляете класс ArrayList, это довольно бессмысленно, поскольку вы на самом деле не хотите сравнивать массивы. Если он находится в классе, хранящемся в ArrayList, вы хотите вернуть -1, если объект this находится перед переданным объектом, -1, если объект this находится после, и 0, если они равны. Если вы можете выбрать свою структуру данных, возможно, вам захочется рассмотреть связанный список: их очень легко добавлять и удалять из них.
Если вы расширяете класс ArrayList, то это очень (каламбур) просто. В вашем методе add вы должны определить местоположение для добавления элемента, затем вызвать метод super.add(int loc)
Ответ №4:
Добавление элемента в правильном положении — это то же самое, что не выполнить двоичный поиск и записать последнюю позицию, которую вы сравнивали.
Ознакомьтесь с документацией по Arrays.BinarySearch. Надеюсь, это даст достаточно информации для его реализации. Ваша реализация comparable должна быть такой же, какую вы использовали бы для сортировки. Вот соответствующий отрывок из документации:
индекс ключа поиска, если он содержится в массиве; в противном случае, (-(точка вставки) — 1). Точка вставки определяется как точка, в которой ключ будет вставлен в массив: индекс первого элемента больше ключа или.длина, если все элементы в массиве меньше указанного ключа. Обратите внимание, что это гарантирует, что возвращаемое значение будет >= 0 тогда и только тогда, когда ключ найден.