Структура данных для конкретной проблемы?

Question

Какая структура данных может выполнить операцию вставки, удаления и поиска за O (1) раз в худшем случае?

Можно предположить, что набор элементов является целым числом, взятым из конечного набора 1,2, ..., n, и инициализация может занять O (n) времени.

Я могу думать только о реализации хеш-таблицы.

Реализация этого с Trees не даст O (1) временной сложности для какой-либо операции. Или это возможно ??

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

Спасибо ..

Answer 1

Хотя это звучит как домашнее задание, при наличии достаточного количества памяти вы можете просто использовать массив. Доступ к любому элементу будет O (1). Если вы используете каждую ячейку для подсчета количества найденных целых чисел этого типа, вставка также будет равна O (1). Поиск будет O (1), потому что это потребует индексации массива по этому индексу и просмотра количества. Вот как работает сортировка по основанию.

Answer 2

В зависимости от диапазона элементов, который может выполнять массив, но для большого количества данных требуется хеш-таблица. Это даст вам (1) амортизированных операций.