Структура данных, чтобы найти количество целых чисел в некотором диапазоне в постоянном времени

Question

Скажем, у меня есть массив из n целых чисел, мне нужно создать структуру данных, которая позволит мне найти количество целых чисел в некотором диапазоне [a, b] в массиве.

Я думал, что некоторыеформа подсчета сортировки?

Answer 1

Да, подсчет части алгоритма сортировки подсчета работает для вас. Что по сути, что Кролик сказал.

Answer 2

Любой эффективный алгоритм поиска потребует отсортированных входных данных.Затем вы можете легко получить ограничивающие индексы за время O (log (n)).

Получение постоянного времени, вероятно, может быть достигнуто только путем создания таблицы поиска.Если вы знаете границы для a и b, это не должно быть слишком сложно.Вы будете торговать эффективностью времени для пространства памяти.Угадай, что ты имеешь в виду под "подсчетом сортировки".

Answer 3

Быстрая сортировка массива.Двоичный поиск, чтобы найти.Перебирайте массив от a до тех пор, пока не найдете b.

Я предполагаю, что вы хотите сделать это без сортировки, потому что в противном случае вопрос слишком прост.

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