719. Encuentre la K-ésima distancia del par más pequeño

Dificultad: Difícil

Temas: Matriz, dos punteros, búsqueda binaria, clasificación

La distancia de un par de números enteros a y b se define como la diferencia absoluta entre a y b.

Dada una matriz de números enteros y un número entero k, devuelve la k^ésima distancia más pequeña entre todos los pares números[i] y números[j] donde 0 .

Ejemplo 1:

• Entrada: números = [1,3,1], k = 1
• Salida: 0
• Explicación: Aquí están todos los pares:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

Entonces el 1^st par de distancias más pequeño es (1,1), y su distancia es 0.

Ejemplo 2:

• Entrada: números = [1,1,1], k = 2
• Salida: 0

Ejemplo 3:

• Entrada: números = [1,6,1], k = 3
• Salida: 5

Restricciones:

• n == números.longitud
• 2 4
• 0 6
• 1

Pista:

1. Búsqueda binaria de la respuesta. ¿Cómo puedes comprobar cuántos pares tienen una distancia

Solución:

Podemos utilizar una combinación de búsqueda binaria y técnica de dos punteros. A continuación se muestra un enfoque paso a paso para resolver este problema:

Acercarse:

1. Ordenar la matriz: Primero, ordene los números de la matriz. La clasificación ayuda a calcular de manera eficiente la cantidad de pares con una distancia menor o igual a un valor determinado.

2. Búsqueda binaria por distancia: utilice la búsqueda binaria para encontrar la k-ésima distancia más pequeña. El espacio de búsqueda de distancias varía desde 0 (la distancia más pequeña posible) hasta max(nums) - min(nums) (la mayor distancia posible).

3. Contar pares con distancia ≤ Mid: para cada valor mid en la búsqueda binaria, cuente el número de pares con una distancia menor o igual a mid. Esto se puede hacer de manera eficiente utilizando un enfoque de dos puntos.

4. Ajustar rango de búsqueda binaria: Dependiendo del número de pares con una distancia menor o igual a la mitad, ajuste el rango de búsqueda binaria. Si el recuento es menor que k, aumente el límite inferior; de lo contrario, disminuya el límite superior.

Implementemos esta solución en PHP: 719. Encuentre la K-ésima distancia del par más pequeño

Explicación:

• countPairsWithDistanceLessThanOrEqualTo: Esta función cuenta cuántos pares tienen una distancia menor o igual a mid. Utiliza dos punteros, donde la derecha es el elemento actual y la izquierda se ajusta hasta que la diferencia entre nums[right] y nums[left] sea menor o igual que mid.

• smallestDistancePair: esta función utiliza la búsqueda binaria para encontrar la k-ésima distancia más pequeña. Los valores bajo y alto definen el rango de búsqueda actual para las distancias. El valor medio se verifica utilizando la función countPairsWithDistanceLessThanOrEqualTo. Dependiendo del resultado se ajusta el espacio de búsqueda.

Este algoritmo encuentra eficientemente la k-ésima distancia de par más pequeña con una complejidad temporal de O(n log(max(nums) - min(nums)) n log n).

Enlaces de contacto

Si esta serie te resultó útil, considera darle al repositorio una estrella en GitHub o compartir la publicación en tus redes sociales favoritas. ¡Tu apoyo significaría mucho para mí!

Si quieres más contenido útil como este, no dudes en seguirme:

• LinkedIn
• GitHub