std::set обычно представлен бинарным деревом поиска. У него есть методы begin и end, которые позволяют получить минимум и максимум, а также lower_bound и upper_bound для бинарного поиска. А что если мне надо получить итератор, указывающий на элемент в середине сета (или один из них, если в нём чётное число элементов)?
Есть ли эффективный способ сделать это (за O(log(size)) вместо O(size))?
{1} => 1
{1,2} => 1 или 2
{1,2,3} => 2
{1,2,3,4} => 2 или 3 (но в ту же сторону от середины, что и с {1,2})
{1,312,10000,14000,152333} => 10000
PS: Этот вопрос на английском.
Ответ
Или, если все-таки использовать set, то можно поддерживать итератор, указывающий на медианный элемент и число элементов k до этого итератора.
Изначально set пустой, итератор равен set.end(), k равно нулю
При добавлении элемента в set:
новый элемент больше медианного => при необходимости (если k * 2 + 3 <= set.size()) сдвигааем итератор на один вперед и увеличиваем k на единицу.
новый элемент меньше медианного => при необходимости сдвигааем итератор на один назад и уменьшаем k на единицу.
При удалении элемента из set действуем аналогично, при необходимости двигаем итератор на единицу вперед/назад
Таким образом, в любой момент времени у нас есть итератор на медианный элемент, дополнительные расходы для поддержания этого итератора составляют O(log n) на каждую операцию вставки/удаления
И еще вот полезный вопрос на английском Stack Overflow примерно про это же (там без удаления, но идея такая же)
Комментариев нет:
Отправить комментарий