Find Median from Data Stream

Q: Qual é a complexidade de tempo de Find Median from Data Stream?

Com dois heaps, addNum é O(log n) , com no máximo três inserções ou remoções de heap, e findMedian é O(1) , com duas leituras. Cada valor é armazenado, então o espaço é O(n) . Ordenar a cada consulta custa O(n log n) por findMedian .

Q: Por que não manter os valores em um array ordenado?

Um array ordenado responde a findMedian em O(1) , e a busca binária encontra onde um novo valor deve ser inserido em O(log n) . Mas inseri-lo desloca todos os valores depois desse ponto, O(n) por addNum .

DifícilHeap

+10

Projete uma estrutura com duas operações: addNum armazena um número inteiro, e findMedian retorna a mediana de todos os valores armazenados até então. A mediana de uma quantidade ímpar é o valor do meio; para uma quantidade par, é a média dos dois valores do meio.

A operação i é ops[i], com values[i] contendo o número para um addNum e 0 para um findMedian. Execute-as em ordem em uma estrutura vazia e retorne uma string para cada operação: "null" para addNum, a mediana para findMedian. Escreva a mediana como "3", "2.5" ou "-0.5": sem ponto decimal para um número inteiro, e zero como "0", nunca "-0".

Função

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

opsstring-array: as operações, na ordem em que são executadas
valuesinteger-array: o número para cada addNum, 0 para cada findMedian
Retornastring-array: uma resposta por operação, como texto

Restrições

1 ≤ ops.length ≤ 3000
values.length == ops.length
Todo ops[i] é addNum ou findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ para addNum, e values[i] == 0 para findMedian.
findMedian só é chamada depois de pelo menos uma chamada a addNum.

Exemplos

Entrada: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Saída: ["null", "5", "null", "3", "null", "5", "null", "4"]
Explicação: Com 1 e 5, a mediana é (1 + 5) / 2 = 3. Com 1, 5 e 8, ela é 5, e com 1, 3, 5 e 8, é (3 + 5) / 2 = 4.

Para ir além

Se todos os valores estivessem entre 0 e 100, como você poderia fazer ambas as operações serem executadas em tempo constante?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A mediana fica entre as duas metades dos dados, então a ordem dentro de cada metade não importa: apenas o maior valor da metade inferior e o menor da superior importam. Dois heaps mantêm exatamente esses dois valores no topo. Cada addNum custa O(log n) e cada findMedian lê os dois valores do topo em O(1).

Ordenação em cada findMedian

Intuição

Armazene cada valor em uma lista. findMedian ordena a lista e lê os índices (total-1)/2 e total/2, com divisão inteira: o mesmo índice para uma quantidade ímpar, o par do meio para uma quantidade par. Some os dois valores e divida a soma pela metade; assim, você obtém a mediana em ambos os casos.

Divida usando inteiros. Uma soma par é divisível exatamente. Uma soma ímpar se torna metade do seu valor absoluto seguida de .5, com o sinal da soma; assim, -3 se torna -1.5.

cada consulta ordena novamente. Com 1.500 adições e uma consulta após cada uma, isso dá cerca de 10^7 comparações, enquanto os heaps precisam de algumas dezenas de milhares de etapas.

Algoritmo

Mantenha uma lista values.
Para addNum x, acrescente x e registre "null".
Para findMedian, ordene values e some values[(total-1)/2] e values[total/2].
Divida a soma pela metade como texto usando inteiros e registre-a.

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

Dois heaps divididos na mediana

Intuição

Divida os valores em uma metade inferior low e uma metade superior high, de modo que cada valor de low seja no máximo igual a cada valor de high, e que low tenha o mesmo tamanho que high ou um elemento a mais. A mediana é o maior valor de low ou, quando a quantidade de valores é par, a média desse valor com o menor valor de high. Um max-heap para low e um min-heap para high mantêm esses valores no topo.

Um novo valor vai para low se for menor ou igual ao valor no topo de low; caso contrário, vai para high. Quando os tamanhos ficam desequilibrados, mova um valor do topo de uma metade para a outra: ele é o valor mais próximo da outra metade, então a ordem é mantida. Uma adição requer algumas operações de heap, O(log n), ou O(n) em R, que copia o heap a cada alteração.

Após as quatro adições do primeiro exemplo, low contém 3 e 1, e high contém 5 e 8.

Algoritmo

Mantenha uma max-heap low para a metade inferior e uma min-heap high para a metade superior.
addNum x: insira x em low se low estiver vazia ou se x for menor ou igual ao topo dela; caso contrário, insira em high.
Se low tiver dois valores a mais que high, mova o topo de low para high. Se high tiver mais valores que low, mova o topo de high para low.
findMedian: se low for maior, registre seu topo. Caso contrário, some os dois topos e divida a soma por dois usando divisão inteira.

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

Armadilhas e casos extremos

Escolher o heap pelo tamanho em vez de pelo valor. Inserir no heap menor sem comparar quebra a ordem entre as duas metades, e os valores no topo deixam de ser os valores do meio.
Dividir pela metade usando divisão inteira simples. Em C e Java, -1 / 2 é 0, então acrescentar .5 imprime 0.5 para -0.5. Em Python, -3 // 2 é -2, o que imprime -2.5 para -1.5. Em algumas linguagens, ponto flutuante imprime 3.0 ou 2.500000.
Armazenar low com o sinal invertido em um heap mínimo e esquecer de inverter o sinal novamente ao ler seu topo ou mover um valor para high.
Escrever -0. Os valores do meio, -1 e 1, somam 0, e a resposta é "0".

Perguntas frequentes3

Qual é a complexidade de tempo de Find Median from Data Stream?

Com dois heaps, addNum é O(log n), com no máximo três inserções ou remoções de heap, e findMedian é O(1), com duas leituras. Cada valor é armazenado, então o espaço é O(n). Ordenar a cada consulta custa O(n log n) por findMedian.

Por que não manter os valores em um array ordenado?

Um array ordenado responde a findMedian em O(1), e a busca binária encontra onde um novo valor deve ser inserido em O(log n). Mas inseri-lo desloca todos os valores depois desse ponto, O(n) por addNum.

Você consegue encontrar a mediana exata de um fluxo sem armazenar todos os valores?

Não em geral. Qualquer valor visto até agora pode se tornar a mediana mais tarde, dependendo do que chegar em seguida; portanto, uma resposta exata precisa de todos eles.

def medianStreamOps(ops, values):
    # Escreva o código aqui

Teste #1

Teste #2

Argumentos

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

Saída Esperada

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