Нахождение k наибольших элементов в массиве за O (1) раз

Question

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

Answer 1

вы можете попробовать ссылку ниже, чтобы обсудить поиск наибольшего числа https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

Answer 2

Да, можно узнать K-й по величине элемент или наименьший элемент по сложности O (1), только если ваш массив находится в отсортированном порядке.

Answer 3

Если вы ищете хорошо известную структуру данных, вы можете найти Max-Heap и Min-Heap полезными.Вы можете узнать больше об этом здесь .

Обновление

Поскольку вы обновили свой вопрос с максимальных и минимальных до самых больших k, вы можете выполнить предварительную обработкуваши данные в отсортированный массив, а затем вставить новое значение, используя стратегию сортировки вставки.Затем вы можете сообщить самое большое значение k в O(k) (а если k является постоянным, оно будет в O(1)).