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