Pares con la menor diferencia
La misión
Problema
Un servicio de medición de tiempos registra las marcas de tiempo de eventos y quiere los pares de eventos que ocurrieron más cerca entre sí. Dada una lista de al menos dos enteros distintos, encuentra la menor diferencia absoluta entre dos de ellos y devuelve cada par [a, b] con a < b que tenga esa diferencia, en orden ascendente de a. La lista tiene hasta 100 000 valores, así que revisar cada par es demasiado lento.
Ejemplos
Input: nums = [4, 2, 1, 3]
Output: [[1, 2], [2, 3], [3, 4]]
Por qué: la menor diferencia es 1, y tres pares la tienen
Input: nums = [3, 8, -10, 23, 19, -4, -14, 27]
Output: [[-14, -10], [19, 23], [23, 27]]
Input: nums = [1, 3, 6, 10, 15]
Output: [[1, 3]]
Por qué: caso límite: solo un par tiene la menor diferencia
Pistas
0 / 3
Comparar cada par es cuadrático. Después de ordenar, ¿qué pares pueden ser los más cercanos?
En una lista ordenada, el valor más cercano a cualquier otro es uno de sus vecinos; cualquier valor más alejado está al menos igual de lejos.
Ordena y luego recorre los pares de vecinos dos veces: una para encontrar la menor diferencia y otra para reunir cada par con esa diferencia. Los pares salen en orden de a sin esfuerzo extra.
- Tiempo objetivo
- O(n log n)
- Espacio objetivo
- O(n)
Restricciones
- 2 ≤ nums.length ≤ 10⁵
- values are distinct integers
Solución
El ordenamiento (sorting) es la herramienta correcta siempre que una pregunta trata de valores cercanos entre sí, porque pone los valores cercanos uno al lado del otro. En una lista ordenada, la diferencia entre un valor y cualquier valor posterior es al menos la diferencia con su vecino inmediato, así que solo hay que revisar los n - 1 pares de vecinos. Un recorrido encuentra la menor diferencia y un segundo reúne los pares que la tienen, ya en orden ascendente. El ordenamiento domina, así que el tiempo es O(n log n) y el espacio extra es O(n) por la copia ordenada y la respuesta.
def smallest_gap_pairs(nums):
s = sorted(nums)
best = min(b - a for a, b in zip(s, s[1:])) # only neighbours can win
return [[a, b] for a, b in zip(s, s[1:]) if b - a == best]
print(smallest_gap_pairs([4, 2, 1, 3])) # -> [[1, 2], [2, 3], [3, 4]]
print(smallest_gap_pairs([3, 8, -10, 23, 19, -4, -14, 27])) # -> [[-14, -10], [19, 23], [23, 27]]
print(smallest_gap_pairs([1, 3, 6, 10, 15])) # -> [[1, 3]]¿Lo que te frena es la idea y no el código? ¿Qué ordenamiento usar y cuándo? lo explica.