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

У вас есть пустой набор. Теперь элементы помещаются в набор один за другим. Мы предполагаем, что все элементы являются целыми числами, и они различны (в соответствии с определением множества, мы неt рассмотреть два элемента с одинаковым значением).

Каждый раз, когда новый элемент добавляется в набор, набор 'Спрашивается среднее значение. Среднее значение определяется так же, как в математике: средний элемент в отсортированном списке. Здесь, в частности, когда размер набора четный, предполагая, что размер набора = 2 * x, медианный элемент является x-м элементом набора.

Пример: начните с пустого набора, когда добавляется 12, медиана равна 12, когда добавляется 7, медиана равна 7, когда добавляется 8, медиана равна 8, когда добавляется 11, медиана равна 8, когда 5 добавляется, медиана равна 8, при добавлении 16 медиана равна 8, ...

Обратите внимание, что, во-первых, элементы добавляются для установки один за другим, а во-вторых, мы неНе знаю, какие элементы будут добавлены.

Мой ответ.

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

Наибольшее время сложность: log_n + n + 1.

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

СЛОЖНОЕ ВРЕМЕНИ сложность: n + 1 + n / 2.

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

Если дерево поддерживается должным образом, гарантируется, что МИРОВАЯ временная сложность равна O (n).

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

Так что мне действительно интересно, будет ли сублинейный алгоритм для этой задачи и если да, то как он будет выглядеть. Есть идеи, ребята?

Стив.