Kth Largest Element in a Stream

Q: ¿Por qué usar un montículo mínimo y no un montículo máximo para el k-ésimo elemento más grande?

El menor de los k valores más grandes es tanto la respuesta como el valor que un recién llegado tiene que superar, y un montículo mínimo de tamaño k lo mantiene en la cima. Un montículo máximo con todos los valores pone el más grande en la cima, así que para llegar al k -ésimo hay que extraer k-1 valores y volver a insertarlos cada vez que llega uno nuevo.

Q: ¿Cuál es la complejidad temporal de Kth Largest Element in a Stream?

Cada llegada cuesta O(log k) : una comparación con el elemento superior y, como máximo, un ajuste descendente a través de un montículo de k valores. Construir el montículo a partir de nums cuesta O(n log k) , así que la ejecución completa requiere un tiempo de O((n + m) log k) y un espacio adicional de O(k) .

FácilMontículo

+10

Una secuencia de enteros comienza con los valores de nums. Después, los valores de adds llegan de uno en uno. Después de cada llegada, registra el valor más grande en la posición k entre todos los valores vistos hasta el momento, contando los valores iguales por separado. Devuelve los valores registrados en orden, uno por cada valor de adds.

nums contiene al menos k-1 valores, así que después de la primera llegada siempre hay al menos k valores entre los que elegir.

Función

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

kinteger: el rango que se debe informar, 1 para el valor más grande
numsinteger-array: los valores que ya están en el flujo
addsinteger-array: los valores que llegan, en orden
Devuelveinteger-array: el k-ésimo valor más grande después de cada llegada

Restricciones

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums puede estar en cualquier orden, y los valores iguales cuentan como valores separados.

Ejemplos

Entrada: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Salida: [3, 5, 6, 6, 7]
Explicación: Después de que llega el 3, el tercero más grande de 7, 5, 3 y 1 es 3. Después, el 9 lo eleva a 5, el 6 lo eleva a 6, el 2 no cambia nada y el 8 lo eleva a 7 (9, 8, 7).

Entrada: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Salida: [-2, 0, 0, 4]
Explicación: Con k = 1, la respuesta es el valor más grande hasta el momento: -2 hasta que llega 0, sigue siendo 0 después de -1 y, luego, 4.

Para ir más allá

¿Cómo responderías a la misma pregunta si también se pudieran eliminar valores del flujo?

Pistas

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

0 de 3 abiertas

Solución

Los valores nunca salen del flujo, por lo que un valor que queda por debajo del k-ésimo mayor queda descartado definitivamente. Conserva solo los k valores más grandes en un montículo mínimo: su cima es la respuesta, y cada llegada cuesta una comparación y, como máximo, una actualización del montículo de O(log k).

Ordena después de cada llegada

Correcto, pero no termina con las pruebas más grandes

Intuición

Mantén cada valor en una lista. Después de cada llegada, ordénala en orden creciente y lee el índice length-k, que por definición es el k-ésimo mayor.

Cada llegada ordena hasta n + m valores, donde n y m son las longitudes de nums y adds. Con 10^4 de cada uno, eso supone unos 2 × 10^9 comparaciones en total.

Algoritmo

Copia nums en una lista values.
Para cada valor de adds, añádelo a values.
Ordena values en orden creciente y registra values[length-k].
Devuelve los 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 de los k valores más grandes

Intuición

Una vez que un valor tiene k valores mayores por encima, eso sigue siendo cierto durante el resto del flujo, así que solo importan los k valores más grandes vistos hasta el momento. Guárdalos en un montículo mínimo. Su cima es el menor de los k valores más grandes, que es exactamente el k-ésimo mayor en total.

Cuando llega x y el montículo está lleno, compáralo con la cima. Si x no es mayor, no está entre los k valores más grandes y nada cambia. Si es mayor, la cima sale: reemplázala por x y húndela, en O(log k). Los valores iniciales siguen la misma rutina, así que nums puede ser más largo que k.

En el primer ejemplo, el montículo contiene 7, 1 y 5 después de nums, con 1 en la cima. La llegada de 3 reemplaza a 1, y la cima, 3, es la primera respuesta.

Algoritmo

Empieza con un montículo mínimo vacío.
Para añadir x: si el montículo contiene menos de k valores, inserta x. De lo contrario, si x es mayor que el elemento superior, reemplaza el elemento superior por x y restablece el orden del montículo.
Añade de esta manera cada valor de nums.
Para cada valor de adds, añádelo y registra el elemento superior del montículo.
Devuelve los 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

Errores comunes y casos límite

Eliminar duplicados. Los cuatro valores más grandes de 9, 6, 6, 6, 2 son 9, 6, 6 y 6. Un conjunto, o una comprobación que omita los valores que ya están presentes, devuelve 2 en el tercer ejemplo en lugar de 6.
Leer la respuesta antes de añadir. Cuando nums contiene k-1 valores, el montículo solo está lleno después de la primera llegada, así que primero añade y después lee el elemento superior.
Contar desde el extremo equivocado después de ordenar. En orden creciente, el elemento más grande número k está en el índice length-k; el índice k-1 contiene el elemento más pequeño número k.
Usar el orden predeterminado del montículo. priority_queue de C++ y BinaryHeap de Rust son montículos máximos: pasa greater<int> o envuelve los valores en Reverse.

Preguntas frecuentes3

¿Por qué usar un montículo mínimo y no un montículo máximo para el k-ésimo elemento más grande?

El menor de los k valores más grandes es tanto la respuesta como el valor que un recién llegado tiene que superar, y un montículo mínimo de tamaño k lo mantiene en la cima. Un montículo máximo con todos los valores pone el más grande en la cima, así que para llegar al k-ésimo hay que extraer k-1 valores y volver a insertarlos cada vez que llega uno nuevo.

¿Cuál es la complejidad temporal de Kth Largest Element in a Stream?

Cada llegada cuesta O(log k): una comparación con el elemento superior y, como máximo, un ajuste descendente a través de un montículo de k valores. Construir el montículo a partir de nums cuesta O(n log k), así que la ejecución completa requiere un tiempo de O((n + m) log k) y un espacio adicional de O(k).

¿Se puede resolver el K-ésimo elemento más grande en un flujo con una lista ordenada?

Sí. Mantén todos los valores ordenados, inserta cada llegada en su lugar mediante búsqueda binaria y lee el valor que está k posiciones desde el final. La búsqueda es O(log n), pero desplazar los valores después del punto de inserción es O(n) por llegada: unos 1.5 × 10^8 desplazamientos para 10^4 valores iniciales y 10^4 llegadas.

def kthLargestStream(k, nums, adds):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

[3, 5, 6, 6, 7]