Подтвердить что ты не робот

Найти медианное значение из растущего набора

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

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

Каждый раз, когда в набор добавляется новый элемент, задается заданное медианное значение. Среднее значение определяется так же, как и в математике: средний элемент в отсортированном списке. Здесь, особенно, когда размер множества четный, если предположить размер множества = 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.

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

Если дерево поддерживается должным образом, гарантируется, что сложность времени WORST равна O (n).

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

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

Steve.

4b9b3361

ОТВЕТЫ

Ответ 1

Ваш анализ сложности запутан. Скажем, что добавлено n предметов; мы хотим вывести поток n медианов (где ith в потоке является медианным для первых элементов i) эффективно.

Я полагаю, что это можно сделать в O (n * lg n) времени, используя две очереди приоритетов (например, двоичную или кукушку фибоначчи); одна очередь для предметов ниже текущей медианной (так что наибольший элемент находится наверху), а другой для элементов над ним (в этой куче наименьшее находится внизу). Обратите внимание, что в фибоначчи (и других) кучах вставка O (1) амортизируется; он только выскакивает элемент, что O (lg n).

Это будет называться алгоритмом онлайн-медианного выбора, хотя Wikipedia говорит только о онлайн-выборе min/max. Здесь приблизительный алгоритм и нижняя граница по детерминированным и приблизительный онлайн-выбор медианного выбора (нижняя граница означает, что не может быть более быстрый алгоритм!)

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

Ответ 2

Я получил тот же вопрос с интервью и придумал решение с двумя кучами в штыревом штыре. По его словам, время на операцию составляет O (log n) в худшем случае. Ожидаемое время также равно O (log n), потому что вы должны "набрать элемент" 1/4 времени, предполагая случайные входы.

Я впоследствии подумал об этом и понял, как получить постоянное ожидаемое время; действительно, ожидаемое количество сравнений на элемент становится 2 + o (1). Вы можете увидеть мою запись в http://denenberg.com/omf.pdf.

BTW, обсуждаемые здесь решения требуют пространства O (n), так как вы должны сохранить все элементы. Совершенно другой подход, требующий только O (log n) пространства, дает вам приближение к медианной (а не точной медианной). Извините, я не могу опубликовать ссылку (я ограничена одной ссылкой за сообщение), но в моей статье есть указатели.

Ответ 3

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

  • Мы используем двоичное дерево поиска, которое сбалансировано (AVL/Red-Black/etc), но не супербалансировано, как вы описали. Таким образом, добавление элемента O (log n)
  • Одна модификация дерева: для каждого node мы также сохраняем количество узлов в своем поддереве. Это не меняет сложность. (Для листа этот счет будет равен 1, для node с двумя листовыми дочерними элементами это будет 3 и т.д.).

Теперь мы можем получить доступ к наименьшему элементу Kth в O (log n), используя эти значения:

def get_kth_item(subtree, k):
  left_size = 0 if subtree.left is None else subtree.left.size
  if k < left_size:
    return get_kth_item(subtree.left, k)
  elif k == left_size:
    return subtree.value
  else: # k > left_size
    return get_kth_item(subtree.right, k-1-left_size)

Медиана - это частный случай наименьшего элемента Kth (учитывая, что вы знаете размер набора).

Итак, все это другое решение O (log n).

Ответ 4

Мы можем определить минимальную и максимальную кучу для хранения чисел. Кроме того, мы определяем класс DynamicArray для набора чисел с двумя функциями: Insert и Getmedian. Время вставки нового номера - O (lgn), а время для получения медианы - O (1).

Это решение реализовано на С++ следующим образом:

template<typename T> class DynamicArray
{
public:
    void Insert(T num)
    {
        if(((minHeap.size() + maxHeap.size()) & 1) == 0)
        {
            if(maxHeap.size() > 0 && num < maxHeap[0])
            {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

                num = maxHeap[0];

                pop_heap(maxHeap.begin(), maxHeap.end(), less<T>());
                maxHeap.pop_back();
            }

            minHeap.push_back(num);
            push_heap(minHeap.begin(), minHeap.end(), greater<T>());
        }
        else
        {
            if(minHeap.size() > 0 && minHeap[0] < num)
            {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<T>());

                num = minHeap[0];

                pop_heap(minHeap.begin(), minHeap.end(), greater<T>());
                minHeap.pop_back();
            }

            maxHeap.push_back(num);
            push_heap(maxHeap.begin(), maxHeap.end(), less<T>());
        }
    }

    int GetMedian()
    {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0)
            throw exception("No numbers are available");

        T median = 0;
        if(size & 1 == 1)
            median = minHeap[0];
        else
            median = (minHeap[0] + maxHeap[0]) / 2;

        return median;
    }

private:
    vector<T> minHeap;
    vector<T> maxHeap;
};

Более подробный анализ можно найти в моем блоге: http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html.

Ответ 5

1) Как и в предыдущих предложениях, держите две кучи и кешируйте их соответствующие размеры. Левая куча сохраняет значения ниже медианы, правая куча сохраняет значения выше медианы. Если вы просто отрицаете значения в правой куче, наименьшее значение будет у корня, поэтому нет необходимости создавать специальную структуру данных.

2) Когда вы добавляете новый номер, вы определяете новую медиану от размера двух ваших кучек, текущей медианы и двух корней кучек L & R, которые просто занимают постоянное время.

3) Вызовите метод private threaded для выполнения фактической работы для выполнения вставки и обновления, но немедленно возвращайтесь к новому медианному значению. Вам нужно только блокировать до тех пор, пока не будут обновлены корни кучи. Затем нить, выполняющая вставку, должна поддерживать блокировку для дедушки-бабушки node, когда она пересекает дерево; это приведет к тому, что вы можете вставлять и балансировать, не блокируя другие вставляющие потоки, работающие с другими подразделами.

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

Rob

Ответ 6

Сбалансированное дерево (например, дерево R/B) с дополненным полем размера должно найти медианное значение в lg (n) раз в худшем случае. Я думаю, что это в главе 14 классического учебника по алгоритму.

Ответ 7

Чтобы вести краткое объяснение, вы можете эффективно увеличить BST, чтобы выбрать ключ указанного ранга в O (h), указав при каждом node количество узлов в левом поддереве. Если вы можете гарантировать, что дерево сбалансировано, вы можете уменьшить это до O (log (n)). Подумайте об использовании AVL, сбалансированного по высоте (или грубо сбалансированного красно-черного дерева), тогда вы можете выбрать любую клавишу в O (log (n)). Когда вы вставляете или удаляете node в AVL, вы можете увеличивать или уменьшать переменную, которая отслеживает общее количество узлов в дереве, чтобы определить ранг медианы, которую вы затем можете выбрать в O (log (n)).

Ответ 8

Чтобы найти медиану в линейном времени, вы можете попробовать это (это только пришло мне в голову). Вам нужно сохранять некоторые значения каждый раз, когда вы добавляете номер в свой набор, и вам не нужна сортировка. Вот оно.

typedef struct
{
        int number;
        int lesser;
        int greater;
} record;

int median(record numbers[], int count, int n)
{
        int i;
        int m = VERY_BIG_NUMBER;

        int a, b;

        numbers[count + 1].number = n:
        for (i = 0; i < count + 1; i++)
        {
                if (n < numbers[i].number)
                {
                        numbers[i].lesser++;
                        numbers[count + 1].greater++;
                }
                else
                {
                        numbers[i].greater++;
                        numbers[count + 1].lesser++;
                }
                if (numbers[i].greater - numbers[i].lesser == 0)
                        m = numbers[i].number;
        }

        if (m == VERY_BIG_NUMBER)
        for (i = 0; i < count + 1; i++)
        { 
                if (numbers[i].greater - numbers[i].lesser == -1)
                        a = numbers[i].number;
                if (numbers[i].greater - numbers[i].lesser == 1)
                        b = numbers[i].number;

                m = (a + b) / 2;
        }

        return m;
}

Что это значит, каждый раз, когда вы добавляете число в набор, вы должны теперь узнать, сколько номеров "меньше вашего номера", и сколько у вас чисел "больше вашего номера". Итак, если у вас есть номер с тем же "меньше" и "больше", это означает, что ваш номер находится в самой середине набора, без необходимости сортировать его. В случае, если у вас есть четное количество чисел, у вас может быть два варианта для медианной, поэтому вы просто возвращаете среднее из этих двух. Кстати, это код C, надеюсь, это поможет.