#algorithm #data-structures #stack
#алгоритм #структуры данных #стек
Вопрос:
Возможно ли добиться O (1) временной сложности при нахождении k наибольших или наименьших чисел в массиве, создав класс стека со вспомогательной структурой данных для отслеживания k наибольших / наименьших в каждом push()
и pop()
. Поскольку извлечение равно O (1), верните k элементов в методе get
Комментарии:
1.
O(1)
невозможно. Для извлеченияk
элементов сложность была бы как минимумO(k)
. Было бы возможно получить константу (такую как указатель на массив, содержащийk
элементы).2. Для k == N это тривиально равно O(1).
Ответ №1:
Да, можно определить K-й наибольший элемент или наименьший элемент по сложности O (1), только если ваш массив отсортирован.
Ответ №2:
Если вы ищете хорошо известную структуру данных, вы можете найти Max-Heap
и Min-Heap
полезную. Вы можете найти больше об этом здесь.
Обновить
Поскольку вы обновили свой вопрос с max и min до k наибольших, вы можете предварительно обработать свои данные в отсортированном массиве, а затем вставить новое значение, используя стратегию сортировки по вставке. Затем вы можете сообщить k
наибольшее значение в O(k)
(и если k
значение постоянное, то оно будет в O(1)
).
Ответ №3:
вы можете попробовать ссылку ниже, в которой обсуждается нахождение наибольшего числа https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array /