Имеет ли упорядоченную структуру данных на Java, которая может заменить элемент по определенному индексу, а также имеет метод contains с O (1) временной сложностью ?Структура данных Java с помощью метода set() и O (1) Содержит()
LinkedHashSet - это почти то, что я ищу, но вы не можете устанавливать/заменять элементы по индексу, используя их.
Вы можете использовать хранить элементы в ArrayList и использовать HashMap<ItemType, Integer> на карту от типа элемента к числу элементов классов эквивалентности в List, разрешающие доступ к элементам, используя список с и позволяет проверить, если элемент содержится с помощью
Integer i = map.get(object);
boolean contained = (i != null) && (i > 0);
Обновление карты для добавления элемента:
map.merge(object, 1, Integer::sum);
удаление элемента:
map.computeIfPresent(object, (k, v) -> v > 1 ? v - 1 : null);
Если элемент заменяется в списке, вы можете обращаться в
map.merge(newValue, 1, Integer::sum);
map.computeIfPresent(oldValue, (k, v) -> v > 1 ? v - 1 : null);
Не в стандартных классах Java. Вы можете сделать класс довольно легко, что составляет HashSet и ArrayList.
В два раза больше стоимости памяти. – shmosel
Правда. Но это не хуже LinkedHashSet в этом отношении. –
@shmosel НЕ с удвоенной стоимостью памяти. Дополнительные затраты будут амортизироваться по размеру элементов. Если они целые, то да, это будет относительно дорого. Если они составляют 1000 байт, то дополнительная стоимость будет незначительной. –
Для задания я также должен был работать с содержит и такие, но они были слишком высокие Стоимость. Поэтому я работал над проблемой, просто создав небольшой интерфейс, в котором было 2 метода. «Установите, если в решении», «Am i в решении». в самом классе мне пришлось использовать для них локальную переменную. Не самый элегантный, но эй он работает. Кроме того, содержащийся в отсортированном списке может быть сведен к журналу сложности (n), потому что вы можете выполнять бинарный поиск на нем. Или даже ниже, если вы считаете, что можете использовать 2-3 дерева. Сортировка, низкая стоимость проверки элемента, но без замены индекса:/ – MrKickkiller
вы хотите также удалить в O (1)? – vaxquis
@ vaxquis Было бы неплохо, но не критично. –