632. Los elementos de cubierta de rango más pequeño de K listas

dificultad: duro

temas: matriz, tabla hash, codiciosa, ventana deslizante, clasificación, paja (prioridad cola)

tiene k listas de enteros ordenados en orden no decrente . Encuentre la gama más pequeña que incluye al menos un número de cada una de las listas k.

Definimos el rango [a, b] es más pequeño que el rango [c, d] si b - a o a

Ejemplo 1:

• Entrada: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• output: [20,24]
• Explicación:
  • Lista 1: [4, 10, 15, 24,26], 24 está en el rango [20,24].
  • Lista 2: [0, 9, 12, 20], 20 está en el rango [20,24].
  • Lista 3: [5, 18, 22, 30], 22 está en el rango [20,24].

Ejemplo 2:

• Entrada: nums = [[1,2,3], [1,2,3], [1,2,3]]
• output: [1,1]

restricciones:

• nums.length == k
• 1
• 1
• -10 ⁵ 5
• nums [i] se clasifica en no decrasing orden.

Solución:

podemos usar un min-heap (o cola de prioridad) para rastrear el elemento más pequeño desde cada lista mientras mantenemos una ventana deslizante para encontrar el rango más pequeño que incluye al menos un elemento de cada lista.

Acercarse

1. Min-Heap Initialization : use un min-heap para almacenar los elementos actuales de cada una de las listas k. Cada entrada de montón será una tupla que contenga el valor, el índice de la lista de la que proviene y el índice del elemento en esa lista.
2. Max Value Tracking : realice un seguimiento del valor máximo en la ventana actual. Esto es importante porque el rango está determinado por la diferencia entre el elemento más pequeño (del montón) y el máximo de corriente.
3. iterar hasta el final de las listas : para cada iteración:
   • Extraiga el elemento mínimo del montón
   • Actualice el rango si el rango actual [min_value, max_value] es más pequeño que el rango más pequeño registrado previamente.
   • muévase al siguiente elemento en la lista desde la cual se tomó el elemento mínimo. Actualice el valor máximo y agregue el nuevo elemento al montón
4. terminación : el proceso termina cuando cualquier lista está agotada.

Implementemos esta solución en php: 632. El rango más pequeño que cubre elementos de k listas

Explicación:

1. Heap Initialization :
   • El montón inicial contiene el primer elemento de cada lista. También realizamos un seguimiento del elemento máximo entre los primeros elementos.
2. procesando el montón :
   • Extraiga el elemento mínimo del montón y luego intente extender el rango agregando el siguiente elemento de la misma lista (si está disponible).
   • Después de agregar un nuevo elemento al montón, actualice el maxvalue si el nuevo elemento es más grande.
   • Actualice el rango más pequeño siempre que la diferencia entre MaxValue y MinValue sea menor que el rango registrado anteriormente.
3. Terminación:
   • El bucle se detiene cuando cualquier lista se queda sin elementos, ya que ya no podemos incluir todas las listas en el rango.

Análisis de complejidad

• complejidad de tiempo : o (n * log k), donde n es el número total de elementos en todas las listas, y k es el número de listas. La complejidad proviene de insertar y eliminar elementos del montón.
• Space Complexity : o (k) para almacenar elementos en el montón

Esta solución encuentra eficientemente el rango más pequeño que incluye al menos un número de cada una de las listas ordenadas.

Enlaces de contacto

Si encontró esta serie útil, considere dar el repositorio una estrella en GitHub o compartir la publicación en sus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si desea un contenido más útil como este, no dude en seguirme:

• linkedin
• github