Find Median from Data Stream

Q: ¿Cuál es la complejidad temporal de encontrar la mediana de un flujo de datos?

Con dos montículos, addNum es O(log n) , como máximo tres inserciones o extracciones de montículo, y findMedian es O(1) , dos lecturas. Se almacena cada valor, por lo que el espacio es O(n) . Ordenar en cada consulta cuesta O(n log n) por cada findMedian .

Q: ¿Por qué no mantener los valores en una matriz ordenada?

Un arreglo ordenado responde a findMedian en O(1) , y la búsqueda binaria encuentra dónde va un valor nuevo en O(log n) . Pero insertarlo desplaza todos los valores que vienen después de ese punto, O(n) por cada addNum .

DifícilMontículo

+10

Diseña una estructura con dos operaciones: addNum almacena un entero y findMedian devuelve la mediana de todos los valores almacenados hasta el momento. La mediana de una cantidad impar es el valor del medio; para una cantidad par, es el promedio de los dos valores del medio.

La operación i es ops[i], donde values[i] contiene el número para addNum y 0 para findMedian. Ejecútalas en orden sobre una estructura vacía y devuelve una cadena por cada una: "null" para addNum, la mediana para findMedian. Escribe la mediana como "3", "2.5" o "-0.5": sin punto decimal para un número entero y el cero como "0", nunca "-0".

Función

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

opsstring-array: las operaciones, en el orden en que se ejecutan
valuesinteger-array: el número para cada addNum, 0 para cada findMedian
Devuelvestring-array: una respuesta por operación, como texto

Restricciones

1 ≤ ops.length ≤ 3000
values.length == ops.length
Todo ops[i] es addNum o findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ para addNum, y values[i] == 0 para findMedian.
findMedian solo se llama después de al menos un addNum.

Ejemplos

Entrada: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Salida: ["null", "5", "null", "3", "null", "5", "null", "4"]
Explicación: Con 1 y 5, la mediana es (1 + 5) / 2 = 3. Con 1, 5 y 8 es 5, y con 1, 3, 5 y 8 es (3 + 5) / 2 = 4.

Para ir más allá

Si todos los valores estuvieran entre 0 y 100, ¿cómo podrías hacer que ambas operaciones se ejecutaran en tiempo constante?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La mediana se encuentra entre las dos mitades de los datos, así que el orden dentro de cada mitad no importa: solo importan el valor más grande de la mitad inferior y el más pequeño de la superior. Dos montículos mantienen exactamente esos dos valores en la parte superior. Cada addNum cuesta O(log n) y cada findMedian lee los dos valores superiores en O(1).

Ordenar en cada findMedian

Intuición

Almacena cada valor en una lista. findMedian la ordena y consulta los índices (total-1)/2 y total/2, con división entera: el mismo índice si la cantidad es impar, el par central si es par. Suma los dos valores y divide la suma entre dos, y así obtienes la mediana en ambos casos.

Divide usando enteros. Una suma par se divide exactamente. Una suma impar se convierte en la mitad de su valor absoluto seguida de .5, con el signo de la suma, así que -3 se convierte en -1.5.

Cada consulta vuelve a ordenar. Con 1,500 inserciones y una consulta después de cada una, eso supone alrededor de 10^7 comparaciones, mientras que los montículos necesitan unas decenas de miles de pasos.

Algoritmo

Mantén una lista values.
Para addNum x, añade x y registra "null".
Para findMedian, ordena values y añade values[(total-1)/2] y values[total/2].
Divide la suma entre dos como texto con enteros y regístrala.

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

Dos montículos divididos en la mediana

Intuición

Divide los valores en una mitad inferior low y una mitad superior high, de modo que cada valor de low sea como máximo igual a cada valor de high, y que low tenga el mismo tamaño que high o uno más. La mediana es el valor más grande de low o, si la cantidad es par, el promedio de ese valor y el valor más pequeño de high. Un montículo máximo para low y un montículo mínimo para high mantienen esos valores en la cima.

Un valor nuevo se agrega a low si es como máximo igual al valor de la cima de low; de lo contrario, se agrega a high. Cuando los tamaños se desequilibran, mueve un valor de la cima de un montículo al otro: es el valor más cercano a la otra mitad, por lo que se mantiene el orden. Una operación de agregado requiere unas pocas operaciones de montículo, O(log n), o O(n) en R, que copia el montículo con cada cambio.

Después de las cuatro operaciones de agregado del primer ejemplo, low contiene 3 y 1, y high contiene 5 y 8.

Algoritmo

Mantén un montículo máximo low para la mitad inferior y un montículo mínimo high para la mitad superior.
addNum x: inserta x en low si low está vacío o si x es como máximo igual a su elemento superior; de lo contrario, en high.
Si low contiene dos valores más que high, mueve el elemento superior de low a high. Si high contiene más valores que low, mueve el elemento superior de high a low.
findMedian: si low es más grande, registra su elemento superior. De lo contrario, suma los dos elementos superiores y divide la suma entre dos usando división entera.

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

Errores comunes y casos límite

Elegir el montón por tamaño en lugar de por valor. Insertar en el montón más pequeño sin comparar rompe el orden entre las dos mitades, y los elementos superiores dejan de ser los valores centrales.
Dividir por la mitad con división entera simple. En C y Java, -1 / 2 es 0, así que agregar .5 imprime 0.5 para -0.5. En Python, -3 // 2 es -2, lo que imprime -2.5 para -1.5. En algunos lenguajes, los números de punto flotante se muestran como 3.0 o 2.500000.
Almacenar low negado en un montón mínimo y olvidarse de volver a negarlo al leer su elemento superior o mover un valor a high.
Escribir -0. Los valores centrales -1 y 1 suman 0, y la respuesta es "0".

Preguntas frecuentes3

¿Cuál es la complejidad temporal de encontrar la mediana de un flujo de datos?

Con dos montículos, addNum es O(log n), como máximo tres inserciones o extracciones de montículo, y findMedian es O(1), dos lecturas. Se almacena cada valor, por lo que el espacio es O(n). Ordenar en cada consulta cuesta O(n log n) por cada findMedian.

¿Por qué no mantener los valores en una matriz ordenada?

Un arreglo ordenado responde a findMedian en O(1), y la búsqueda binaria encuentra dónde va un valor nuevo en O(log n). Pero insertarlo desplaza todos los valores que vienen después de ese punto, O(n) por cada addNum.

¿Puedes encontrar la mediana exacta de un flujo sin almacenar todos los valores?

No, en general. Cualquier valor visto hasta ahora puede convertirse en la mediana más adelante, dependiendo de lo que llegue después, así que una respuesta exacta necesita todos esos valores.

def medianStreamOps(ops, values):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumentos

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

Salida Esperada

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