Pular para o conteúdo

Pares com a menor diferença

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

A missão

Problema

Um serviço de medição de tempo registra os timestamps de eventos e quer os pares de eventos que aconteceram mais perto um do outro. Dada uma lista com pelo menos dois inteiros distintos, encontre a menor diferença absoluta entre dois deles e retorne todos os pares [a, b] com a < b que têm essa diferença, listados em ordem crescente de a. A lista tem até 100.000 valores, então verificar todos os pares é lento demais.

Exemplos

Input:  nums = [4, 2, 1, 3]
Output: [[1, 2], [2, 3], [3, 4]]
Por quê: a menor diferença é 1, e três pares a têm
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ê: edge case: só um par tem a menor diferença

Dicas

0 / 3

Tempo-alvo
O(n log n)
Espaço-alvo
O(n)

Restrições

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

Travou na ideia, e não no código? Qual ordenação usar? explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado