режим поиска в скользящем окне длинной последовательности данных с дубликатами

Question

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

Я не могу найти лучшего решения здесь.

Моя идея: Используйте хеш-таблицу, ключ - это данные, ключ - это частота данных, появляющихся в окне.

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

Это O (n * m), где n - размер данных seq, а m - размер окна. Недостатком является то, что размер хеш-таблицы не является фиксированным, возможно, он имеет размер при изменении размера. Каждая итерация, таблица должна быть пройдена, она не эффективна.

Возможно ли сделать это с помощью O (n lg m) или O (n)?

Любая помощь приветствуется.

спасибо

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

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

В появившемся окне получите новые данные, а также обновите хеш-таблицу, обновите мультикарту, добавив новейшую обновленную таблицу в хеш-таблицу.

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

Время O (m + m * lg m + n * lg m), если n >> m, O (n lg m). Пространство: O (м)

Есть идея получше?

Answer 1

Пробел O (M):

• Один кольцевой буфер для хранения значений М.
• Один BST, содержащий пары M {value, PQ pointer}.
• Одна приоритетная очередь, содержащая M, имеет значение.

Обновление во времени O (lg M):

• Найти исходящее значение в кольцевом буфере O(1),
• Найти то же значение в BST O(lg M),
• Настройте количество в связанном узле PQ.
  • Выполните настройку Приоритета на этом узле O(lg M)
• Заменить старую запись кольцевого буфера новой O(1)
• Найти новое значение в BST O(lg M),
• Настройте количество в связанном узле PQ.
  • Выполните настройку Приоритета на этом узле O(lg M)
• GetFirst на PQ для поиска режима O(1)

Вы можете избавиться от кольцевого буфера, добавив указатель nextItem к структуре BST и сохранив внешний указатель на самый старый элемент. Это ускоряет его на один поиск BST и может быть выигрышом в пробелах, если размер значения больше, чем размер указателя. Но алгоритм становится все более сложным для кода.

Answer 2

Возвращаясь к решению предыдущего вопроса ...

Поддерживать кольцевой буфер значений данных.Создайте тип, который является парой частота / значение.

Ведение карты с данными этих пар;сделайте мультикарту с ключом по частоте, также содержащую такие пары.

На каждом шаге, проходящем через данные, режим является последней записью в карте, набранной по частоте.Может быть и галстук - что с этим делать - упражнение для читателя.После сообщения о режиме вам нужно использовать карту, чтобы найти пару, принадлежащую значению, которое нужно удалить;затем извлеките из мультикарты все записи, которые имеют частоту удаления значения, и найдите запись с правильным значением.Удалить, изменить и повторно вставить узлы в карту и мультикарту, чтобы иметь дело с удаленными данными;используйте аналогичный процесс для обработки добавленных данных.В зависимости от ожидаемых данных, возможно, стоит сначала проверить, соответствует ли вставляемое значение тому, которое нужно удалить.