Вопрос структуры данных
Этот вопрос связан с экзаменом, который у меня был, и я не мог его решить и хотел узнать, что такое ответ (это не домашнее задание, поскольку оно не поможет мне ни в чем, кроме знания).
Нам нужно создать структуру данных для содержания элементов, ключи которых являются действительными числами.
Структура данных должна иметь следующие функции:
Build (S, array): строит структуру данных S с n элементами в O (n)
Вставьте (S, k) и Delete (S, x) в O (lgn) (k - элемент, x - указатель на него в структуре данных)
Delete-Minimal-Positive (S): удалить элемент с минимальным положительным ключом
Режим (S): возвращает клавишу, наиболее часто встречающуюся в S в O (1)
Теперь, построение в O (n) обычно означает, что куча должна использоваться, но это не позволяет находить частоты. Я не мог найти никакого способа сделать это. Лучшее, что я мог придумать, заключается в создании Red-Black-Tree (O (nlgn)), который будет использоваться для создания кучи частоты.
Я умираю, чтобы узнать ответ...
Спасибо!
Ответы
Ответ 1
Используя только сравнительную модель, решения этой проблемы не существует.
Проблема отличимости элемента доказывает нижние границы Omega (nlogn). Эта (элементность) проблема в основном заключается в определении того, являются ли все элементы массива различными.
Если бы было решение вашей проблемы, мы могли бы ответить на проблему отличимости элемента в O (n) времени (найти наиболее часто используемый элемент в O (n) времени и посмотреть, есть ли более одного экземпляра этого элемент снова в O (n) времени).
Итак, я предлагаю вам спросить своего профессора для вычислительной модели.
Ответ 2
Хорошо, вы можете использовать хеш-таблицу для вычисления числа вхождений различных действительных чисел в O (1) амортизированном времени, а затем использовать стандартную кучу, где элементы являются парами (действительное число, количество вхождений) и куча сортируется в соответствии с количеством полей вхождения.
Когда вы вставляете ключ или удаляете ключ, вы увеличиваете или уменьшаете количество полей вхождения на единицу или в крайних случаях добавляете или удаляете кучу. В обоих случаях вам необходимо просачиваться вверх/вниз, потому что поле упорядочения изменилось.
Предполагая, что хеш-таблица является операцией O (1), у вас есть стандартная таблица хэшей + O (1), и вы получаете все вышеперечисленные операции в пределах сроков. В частности, вы получаете "режим", читая корневой элемент кучи.
Ответ 3
Я думаю, что следующее решение будет приемлемым. Он основан на двух структурах данных:
- Красно-черное дерево
- Двоичная куча
Двоичная куча держит кортеж, который содержит (значение элемента, частоту элемента), куча построена на частотах, поэтому дает нам возможность находить режим в O (1).
Красное черное дерево содержит кортеж, который удерживает (значение элемента, указатель на одно и то же значение элемента в куче)
Когда вам нужно вставить новый элемент, вы попытаетесь найти элемент (он принимает O (log n)), если поиск был успешным, чем перейти к указателю из элемента, созданного в RB-дереве, увеличить частоту и перестроить куча (также O (log n)). Если поиск не нашел такого элемента, кроме как вставить его в RB-tree (O (log n)) и кучи со значением = (элемент, 1) (также O (1)), установите указатель в дереве RB на новый элемент в куче.
Начальное построение будет принимать O (n), потому что построение обеих структур из набора n элементов принимает O (n).
Извините, если я что-то пропустил.
Ответ 4
Для частот:
Каждая запись двунаправленна, связанная с собственными частотами/счетчиками (используйте хеш-таблицу)
Частоты находятся в связанном списке.
Необходимо переместить частоту вверх/вниз по связанному списку (удаление элемента вставки), но для максимальной разницы в 1.
Таким образом, частоты связаны с указателем на частотный элемент +1 и -1.
(есть исключения, но могут быть обработаны)
