Pares com a menor diferença
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
Comparar todos os pares é quadrático. Depois de ordenar, quais pares podem ser os mais próximos?
Em uma lista ordenada, o parceiro mais próximo de qualquer valor é um dos vizinhos dele; qualquer valor mais distante está pelo menos tão longe quanto.
Ordene e varra os pares vizinhos duas vezes: uma para encontrar a menor diferença e outra para coletar todos os pares com essa diferença. Os pares já saem em ordem de a, sem custo extra.
- Tempo-alvo
- O(n log n)
- Espaço-alvo
- O(n)
Restrições
- 2 ≤ nums.length ≤ 10⁵
- values are distinct integers
Solução
Ordenar é a ferramenta certa sempre que a pergunta é sobre valores próximos entre si, porque a ordenação coloca valores próximos lado a lado. Em uma lista ordenada, a diferença entre um valor e qualquer valor posterior é pelo menos a diferença até o vizinho imediato dele, então só os n - 1 pares vizinhos precisam ser verificados. Uma varredura encontra a menor diferença e uma segunda coleta os pares que a têm, já em ordem crescente. A ordenação domina, então o tempo é O(n log n), e o espaço extra é O(n) pela cópia ordenada e pela resposta.
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]]Travou na ideia, e não no código? Qual ordenação usar? explica isso.