Блог

Главная - Вопросы по программированию - Нахождение k наибольших элементов в массиве за O (1) время

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

#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 /