Saltar al contenido

Pares con la menor diferencia

Fácil#sort-first#adjacent-scan~15 min

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

Tiempo objetivo
O(n log n)
Espacio objetivo
O(n)

Restricciones

  • 2 ≤ nums.length ≤ 10⁵
  • values are distinct integers

¿Lo que te frena es la idea y no el código? ¿Qué ordenamiento usar y cuándo? lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio