Find Median from Data Stream

Q: Какова временная сложность поиска медианы в потоке данных?

При использовании двух куч addNum работает за O(log n) : выполняется не более трёх операций добавления или извлечения из кучи, а findMedian работает за O(1) : выполняются два чтения. Хранятся все значения, поэтому пространственная сложность составляет O(n) . Сортировка при каждом запросе обходится в O(n log n) для каждого вызова findMedian .

Q: Почему бы не хранить значения в отсортированном массиве?

Отсортированный массив вычисляет findMedian за O(1) , а бинарный поиск находит место для нового значения за O(log n) . Но при вставке сдвигается каждое значение после этой позиции — O(n) для каждого addNum .

СложноКуча

+10

Спроектируй структуру с двумя операциями: addNum сохраняет целое число, а findMedian возвращает медиану всех чисел, сохранённых на данный момент. Медиана нечётного количества чисел — это среднее число; для чётного количества — среднее арифметическое двух средних чисел.

Операция i — это ops[i], при этом values[i] содержит число для addNum и 0 для findMedian. Выполни их по порядку для пустой структуры и верни по одной строке для каждой: "null" для addNum, медиану для findMedian. Записывай медиану в виде "3", "2.5" или "-0.5": без десятичной точки для целого числа, а ноль — как "0", никогда как "-0".

Функция

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: операции в порядке их выполнения
valuesinteger-array: число для каждого addNum, 0 для каждого findMedian
Возвращаетstring-array: один ответ на операцию в виде текста

Ограничения

1 ≤ ops.length ≤ 3000
values.length == ops.length
Каждый ops[i] — это addNum или findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ для addNum, а values[i] == 0 для findMedian.
findMedian вызывается только после того, как выполнен хотя бы один вызов addNum.

Примеры

Ввод: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Вывод: ["null", "5", "null", "3", "null", "5", "null", "4"]
Пояснение: Для 1 и 5 медиана равна (1 + 5) / 2 = 3. Для 1, 5 и 8 она равна 5, а для 1, 3, 5 и 8 — (3 + 5) / 2 = 4.

Дополнительный вопрос

Если бы каждое значение находилось в диапазоне от 0 до 100, как можно было бы сделать так, чтобы обе операции выполнялись за постоянное время?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Медиана находится между двумя половинами данных, поэтому порядок элементов внутри каждой половины не имеет значения: важны только наибольшее значение нижней половины и наименьшее значение верхней. Две кучи хранят именно эти два значения наверху. Каждый вызов addNum требует O(log n), а каждый вызов findMedian считывает два верхних элемента за O(1).

Сортируйте при каждом вызове findMedian

Идея

Сохраняй каждое значение в списке. findMedian сортирует список и считывает индексы (total-1)/2 и total/2, используя целочисленное деление: при нечётном количестве это один и тот же индекс, при чётном — пара средних элементов. Сложи два значения и раздели сумму пополам — так ты получишь медиану в обоих случаях.

Деление пополам выполняй с целыми числами. Чётная сумма делится без остатка. Нечётная сумма превращается в половину своего абсолютного значения с добавлением .5 и знаком суммы, поэтому -3 превращается в -1.5.

При каждом запросе сортировка выполняется заново. При 1,500 добавлениях и запросе после каждого из них это около 10^7 сравнений, тогда как кучам требуется несколько десятков тысяч шагов.

Алгоритм

Храни список values.
Для addNum x добавь x в конец и запиши "null".
Для findMedian отсортируй values и добавь values[(total-1)/2] и values[total/2].
Раздели сумму пополам, представив её текстом с целыми числами, и запиши её.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Две кучи разделены по медиане

Идея

Раздели значения на нижнюю половину low и верхнюю половину high, причём каждое значение в low должно быть не больше любого значения в high, а размер low должен быть равен размеру high или на единицу больше. Медиана — это наибольшее значение в low, а при чётном количестве значений — среднее между ним и наименьшим значением в high. Макс-куча для low и мин-куча для high позволяют держать эти значения на вершине.

Новое значение добавляется в low, если оно не больше верхнего значения low, иначе — в high. Когда размеры перестают соответствовать условию, перемести верхнее значение из одной кучи в другую: это значение ближе всего к другой половине, поэтому порядок сохранится. Добавление требует нескольких операций с кучей — O(log n), или O(n) в R, где при каждом изменении копируется куча.

После четырёх добавлений в первом примере в low находятся 3 и 1, а в high — 5 и 8.

Алгоритм

Храните max-heap low для нижней половины и min-heap high для верхней половины.
addNum x: поместите x в low, если low пуст или x не больше его вершины, иначе — в high.
Если в low на два значения больше, чем в high, переместите вершину low в high. Если в high значений больше, чем в low, переместите вершину high в low.
findMedian: если low больше, запишите его вершину. В противном случае сложите две вершины и разделите сумму пополам, используя целочисленное деление.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Ловушки и крайние случаи

Выбор кучи по размеру, а не по значению. Добавление элемента в меньшую кучу без сравнения нарушает порядок между половинами, и вершины перестают быть средними значениями.
Деление пополам с помощью обычного целочисленного деления. В C и Java -1 / 2 равно 0, поэтому добавление .5 выводит 0.5 для -0.5. В Python -3 // 2 равно -2, поэтому для -1.5 выводится -2.5. В некоторых языках числа с плавающей точкой выводятся как 3.0 или 2.500000.
Хранение low со сменённым знаком в минимальной куче и забывание сменить знак обратно при чтении её вершины или перемещении значения в high.
Запись -0. Средние значения -1 и 1 в сумме дают 0, и ответ — "0".

Частые вопросы3

Какова временная сложность поиска медианы в потоке данных?

При использовании двух куч addNum работает за O(log n): выполняется не более трёх операций добавления или извлечения из кучи, а findMedian работает за O(1): выполняются два чтения. Хранятся все значения, поэтому пространственная сложность составляет O(n). Сортировка при каждом запросе обходится в O(n log n) для каждого вызова findMedian.

Почему бы не хранить значения в отсортированном массиве?

Отсортированный массив вычисляет findMedian за O(1), а бинарный поиск находит место для нового значения за O(log n). Но при вставке сдвигается каждое значение после этой позиции — O(n) для каждого addNum.

Сможешь найти точную медиану потока, не сохраняя каждое значение?

Не в общем случае. Любое уже полученное значение позже может стать медианой — в зависимости от того, что поступит дальше, поэтому для точного ответа нужны все значения.

def medianStreamOps(ops, values):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

Ожидаемый вывод

["null", "5", "null", "3", "null", "5", "null", "4"]