вставка, удаление, максимум в O (1)
Может кто-нибудь сказать мне, какая структура данных поддерживает операцию вставки / удаления / максимальной операции в O (1)?
4 ответа
Это классический вопрос для интервью, который обычно задается так:
Разработайте структуру данных, подобную стеку, которая выполняет операции push, pop и min (или max) за время O(1). Ограничений на пространство нет.
Ответ таков: вы используете два стека: основной стек и стек min (или max).
Например, после того, как вы вытолкнули 1,2,3,4,5 в стек, ваши стеки будут выглядеть следующим образом:
MAIN MIN
+---+ +---+
| 5 | | 1 |
| 4 | | 1 |
| 3 | | 1 |
| 2 | | 1 |
| 1 | | 1 |
+---+ +---+
Однако, если вы вытолкнете 5,4,3,2,1, стеки будут выглядеть следующим образом:
MAIN MIN
+---+ +---+
| 1 | | 1 |
| 2 | | 2 |
| 3 | | 3 |
| 4 | | 4 |
| 5 | | 5 |
+---+ +---+
Для 5,2,4,3,1 вы будете иметь:
MAIN MIN
+---+ +---+
| 1 | | 1 |
| 3 | | 2 |
| 4 | | 2 |
| 2 | | 2 |
| 5 | | 5 |
+---+ +---+
и так далее.
Вы также можете сэкономить немного места, выталкивая в стек min только при изменении минимального элемента, если известно, что элементы различны.
Хеш-таблица может поддерживать вставку / удаление в O (1), однако о максимуме не известно. Вам, вероятно, придется как-то следить за этим самому.
Комментарий @ KennyTM указывает на важную недостающую деталь - вставить где и удалить откуда. Итак, я предполагаю, что вы всегда хотите вставлять и удалять только с одного конца, например, стека.
Вставка (нажатие) и удаление (выталкивание) равны O (1).
Чтобы получить максимальное значение за O (1), используйте дополнительный стек для записи текущего максимума, который соответствует основному стеку.
Если вы используете только сравнения, вам будет трудно найти такую структуру данных.
Например, вы можете вставить n элементов, получить max, удалить max и т. Д. И можете сортировать числа во времени O(n), в то время как теоретическая нижняя граница - Omega(nlogn).