Kth Largest Element in a Stream

Q: Por que usar um min-heap e não um max-heap para o k-ésimo maior elemento?

O menor dos k maiores valores é tanto a resposta quanto o valor que um recém-chegado precisa superar, e um heap mínimo de tamanho k o mantém no topo. Um heap máximo de todos os valores coloca o maior no topo, então chegar ao k -ésimo significa remover k-1 valores e inseri-los novamente a cada chegada.

Q: Qual é a complexidade de tempo do K-ésimo maior elemento em um fluxo?

Cada chegada custa O(log k) : uma comparação com o topo e, no máximo, uma operação de ajuste em um heap de k valores. Construir o heap a partir de nums custa O(n log k) , então a execução toda leva O((n + m) log k) de tempo e usa O(k) de espaço extra.

FácilHeap

+10

Um fluxo de números inteiros começa com os valores em nums. Em seguida, os valores de adds chegam um de cada vez. Após cada chegada, registre o k-ésimo maior valor entre tudo o que foi visto até então, contando valores iguais separadamente. Retorne os valores registrados em ordem, um para cada valor de adds.

nums contém pelo menos k-1 valores, portanto, após a primeira chegada, sempre há pelo menos k valores entre os quais escolher.

Função

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: a classificação a relatar, 1 para o maior valor
numsinteger-array: os valores que já estão no fluxo
addsinteger-array: os valores que chegam, em ordem
Retornainteger-array: o k-ésimo maior valor após cada chegada

Restrições

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums pode estar em qualquer ordem, e valores iguais contam como valores separados.

Exemplos

Entrada: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Saída: [3, 5, 6, 6, 7]
Explicação: Depois do 3, o terceiro maior entre 7, 5, 3 e 1 é 3. Em seguida, 9 eleva-o para 5, 6 eleva-o para 6, 2 não altera nada, e 8 eleva-o para 7 (9, 8, 7).

Entrada: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Saída: [-2, 0, 0, 4]
Explicação: Com k = 1, a resposta é o maior valor encontrado até então: -2 até que 0 chegue, continua sendo 0 após -1 e, então, 4.

Para ir além

Como você responderia à mesma pergunta se os valores também pudessem ser removidos do fluxo?

Dicas

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

0 de 3 abertas

Solução

Os valores nunca saem do fluxo, então um valor que fica abaixo do k-ésimo maior está descartado para sempre. Mantenha apenas os k maiores valores em um min-heap: o topo é a resposta, e cada chegada custa uma comparação e, no máximo, uma atualização do heap de O(log k).

Ordene após cada chegada

Correta, mas não termina nos maiores testes

Intuição

Mantenha todos os valores em uma lista. Após cada chegada, ordene-a em ordem crescente e leia o índice length-k, o k-ésimo maior por definição.

Cada chegada ordena até n + m valores, em que n e m são os comprimentos de nums e adds. Com 10^4 de cada, isso dá cerca de 2 × 10^9 comparações no total.

Algoritmo

Copie nums para uma lista values.
Para cada valor de adds, adicione-o a values.
Ordene values em ordem crescente e registre values[length-k].
Retorne os valores registrados.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-heap dos k maiores valores

Intuição

Quando um valor tem k valores maiores acima dele, isso continua sendo verdade pelo restante do fluxo; portanto, apenas os k maiores valores vistos até agora importam. Armazene-os em um min-heap. O topo é o menor dos k maiores, que é exatamente o k-ésimo maior no geral.

Quando x chega e o heap está cheio, compare-o com o topo. Se x não for maior, ele não está entre os k maiores e nada muda. Se for maior, o topo sai: substitua-o por x e faça a descida, em O(log k). Os valores iniciais passam pela mesma rotina, então nums pode ser maior que k.

No primeiro exemplo, o heap contém 7, 1 e 5 após nums, com 1 no topo. A chegada de 3 substitui 1, e o topo, 3, é a primeira resposta.

Algoritmo

Comece com um min-heap vazio.
Para adicionar x: se o heap tiver menos de k valores, insira x. Caso contrário, se x for maior que o topo, substitua o topo por x e restaure a ordem do heap.
Adicione todos os valores de nums dessa forma.
Para cada valor de adds, adicione-o e registre o topo do heap.
Retorne os valores registrados.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Armadilhas e casos extremos

Descartar duplicatas. Os quatro maiores valores entre 9, 6, 6, 6, 2 são 9, 6, 6 e 6. Um conjunto, ou uma verificação que ignora valores já presentes, retorna 2 no terceiro exemplo em vez de 6.
Ler a resposta antes de adicionar. Quando nums contém k-1 valores, o heap só fica cheio após a primeira inserção; portanto, adicione primeiro e depois leia o topo.
Contar a partir da extremidade errada após uma ordenação. Em ordem crescente, o k-ésimo maior está no índice length-k; o índice k-1 contém o k-ésimo menor.
Usar a ordem padrão do heap. priority_queue do C++ e BinaryHeap do Rust são max-heaps: passe greater<int> ou envolva os valores em Reverse.

Perguntas frequentes3

Por que usar um min-heap e não um max-heap para o k-ésimo maior elemento?

O menor dos k maiores valores é tanto a resposta quanto o valor que um recém-chegado precisa superar, e um heap mínimo de tamanho k o mantém no topo. Um heap máximo de todos os valores coloca o maior no topo, então chegar ao k-ésimo significa remover k-1 valores e inseri-los novamente a cada chegada.

Qual é a complexidade de tempo do K-ésimo maior elemento em um fluxo?

Cada chegada custa O(log k): uma comparação com o topo e, no máximo, uma operação de ajuste em um heap de k valores. Construir o heap a partir de nums custa O(n log k), então a execução toda leva O((n + m) log k) de tempo e usa O(k) de espaço extra.

É possível resolver o problema do K-ésimo maior elemento em um fluxo com uma lista ordenada?

Sim. Mantenha todos os valores ordenados, insira cada chegada em sua posição usando busca binária e leia o valor k posições a partir do fim. A busca é O(log n), mas deslocar os valores após o ponto de inserção é O(n) por chegada: cerca de 1.5 × 10^8 deslocamentos para 10^4 valores iniciais e 10^4 chegadas.

def kthLargestStream(k, nums, adds):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Saída Esperada

[3, 5, 6, 6, 7]