Структура данных для поиска медианы

Это вопрос интервью. Разработайте класс, который хранит целые числа и обеспечивает две операции:

пустая вставка (int k)
int getMedian()

Я думаю, что я могу использовать BST так, чтобы insert принимает O(logN) и getMedian принимает O(logN) (для getMedian Я должен добавить количество левых / правых детей для каждого узла).

Теперь мне интересно, если это самое эффективное решение, а лучшего нет.

Источник

4 ответа

Решение

Вы можете использовать 2 кучи, которые мы будем называть Left а также Right,
Left это Max-Heap,
Right это Min-Heap,
Вставка делается так:

  • Если новый элемент x меньше корня Left тогда мы вставляем x в Left,
  • Иначе мы вставим x в Right,
  • Если после вставки Left имеет количество элементов, которое больше 1 от количества элементов Right, тогда мы называем Extract-Max на Left и вставьте его в Right,
  • Остальное если после вставки Right имеет количество элементов, которое больше, чем количество элементов Left, тогда мы называем Extract-Min на Right и вставьте его в Left,

Медиана всегда является корнем Left,

Так что вставка делается в O(lg n) время и получение медианы делается в O(1) время.

Источник

Смотрите этот вопрос переполнения стека для решения, которое включает в себя две кучи.

Источник

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

Источник

Будет ли он разбивать массив целых чисел, который выполняет сортировку во время вставки с помощью алгоритма сортировки, предназначенного для целых чисел (http://en.wikipedia.org/wiki/Sorting_algorithm), если вы выберете своего кандидата среди O

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

Я в значительной степени автодидакт в информатике, но я бы так и поступил: проще, тем лучше.

Источник
Другие вопросы по тегам