Структура данных, которая поддерживает запрос наиболее часто встречающихся элементов на основе диапазона

Question

Я ищу структуру данных, с помощью которой я могу найти наиболее часто встречающееся число (среди массива чисел) в заданном диапазоне переменных.

Давайте рассмотрим следующий массив на основе 1:

1 2 3 1 1 3 3 3 3 1 1 1 1

Если я запрашиваю диапазон (1,4), структура данных должна повторить 1, что происходит дважды. Несколько других примеров:

(1,13) = 1

(4,9) = 3

(2,2) = 2

(1,3) = 1 (все 1,2,3 встречаются один раз, поэтому верните первое / наименьшее. В данный момент это не так важно)

Я искал, но не смог найти ничего похожего. Я ищу (в идеале) структуру данных с минимальными требованиями к пространству, быстрой предварительной обработкой и / или сложностями запросов.

Заранее спасибо!

Answer 1

Пусть N будет размером массива, а M - количеством различных значений в этом массиве.

Я рассматриваю две сложности: предварительную обработку и запрос интервала размером n, каждый должен быть пространственным и временным.

---

Решение 1:

• Пространственный: O (1) и O (M)
• Временные: O (1) и O (n + M)

Без предварительной обработки, мы смотрим на все значения интервала и находим наиболее частое.

---

Решение 2:

• Пространственные: O (M * N) и O (1)
• Временные: O (M * N) и O (мин (n, M))

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

Учитывая интервал, нам нужно, чтобы каждый x вычел 2 значения, чтобы найти число x в этом интервале. Итерируем по каждому x и находим максимальное значение. Если n

---

Решение 3:

• Пространственный: O (N) и O (1)
• Временные: O (N) и O (мин (n, M) * log (n))

Для каждого значения x построить двоичную кучу всех позиций в массиве, где присутствует x. Ключ в вашей куче - это позиция, но вы также сохраняете общее число x между этой позицией и началом массива.

Учитывая интервал, который нам нужно, чтобы каждый x вычел 2 значения, чтобы найти число x в этом интервале: в O (log (N)) мы можем попросить кучу x найти две позиции непосредственно перед началом конец интервала и вычесть числа. По сути, для этого требуется меньше места, чем для гистограммы, но теперь запрос в O (log (N)).

Answer 2

Вы можете создать двоичное дерево разделов, где каждый узел представляет карту гистограммы {значение -> частота} для данного диапазона и имеет два дочерних узла, которые представляют верхнюю и нижнюю половины диапазона.

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

Полезные оптимизации включают в себя::

• Использование гистограммы с изменяемой частотой считается "аккумулятором", пока вы добавляете гистограммы вместе
• Прекратите использование предварительно вычисленных гистограмм, как только вы доберетесь до определенного размера (возможно, диапазона меньшечем общее количество возможных значений M) и просто подсчет числа напрямую.Это компромисс между временем и пространством, который, я думаю, окупится большую часть времени.
• Если у вас фиксированное небольшое количество возможных значений, используйте массив, а не карту, чтобы хранить значения частоты вкаждый узел

ОБНОВЛЕНИЕ : мои мысли о сложности алгоритма предполагают ограниченное небольшое количество возможных значений M и всего N значений в полном диапазоне:

• Предварительная обработка: O (N log N) - в основном вам нужно пройти по всему списку и построить двоичное дерево, построив один узел для каждого M элементов, чтобы амортизировать накладные расходы каждого узла
• Запросы: O (M log N) - в основном суммирование гистограмм O (log N) каждого размера M плюс подсчет значений O (M) по обе стороны диапазона
• Требуемое пространство составляет O (N) - прибл.Гистограммы 2N / M каждого размера M. Фактор 2 представляет собой сумму наличия гистограмм N / M на нижнем уровне, гистограмм 0,5N / M на следующем уровне, 0,25N / M на третьем уровне и т. Д ...