Menor distância entre repetições
A missão
Problema
Você recebe uma lista de valores. Entre todos os pares de posições que guardam o mesmo valor, encontre o par mais próximo e retorne a distância entre eles, medida como a diferença dos seus índices. Se nenhum valor aparecer duas vezes, retorne -1.
Exemplos
Input: values = [7, 1, 3, 7, 1, 7]
Output: 2
Por quê: os 7 nos índices 3 e 5 estão a duas posições; os 1 estão a três
Input: values = [3, 8, 8, 3]
Output: 1
Por quê: os dois 8 estão lado a lado
Input: values = [5, 6, 7]
Output: -1
Por quê: edge case: nada se repete
Dicas
0 / 3
Comparar cada par de posições funciona, mas o trabalho cresce com o quadrado do tamanho: dobre a lista e ela leva quatro vezes mais tempo.
Para o valor na posição atual, só uma posição anterior pode dar a menor distância. Qual é ela, e o que permitiria encontrá-la na hora?
Percorra a lista uma vez, mantendo um mapa de cada valor para o último índice em que você o viu. Quando o valor atual já estiver no mapa, compare o índice atual menos o guardado com a melhor distância até agora e, depois, sobrescreva o índice guardado.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
O gêmeo anterior mais próximo de qualquer posição é o mais recente, então basta lembrar o último índice de cada valor. Um hash map responde a essa busca em tempo constante, em média, o que transforma a verificação quadrática de pares em uma única passada. O mapa é atualizado a cada passo, então sempre guarda o índice mais recente de cada valor. O tempo é O(n) em média, e o espaço é O(n) para o mapa.
def closest_repeat(values):
last_seen = {} # value -> most recent index
best = -1
for i, v in enumerate(values):
if v in last_seen:
gap = i - last_seen[v]
if best == -1 or gap < best:
best = gap
last_seen[v] = i # only the latest index can matter later
return best
print(closest_repeat([7, 1, 3, 7, 1, 7])) # -> 2
print(closest_repeat([3, 8, 8, 3])) # -> 1
print(closest_repeat([5, 6, 7])) # -> -1Travou na ideia, e não no código? O que é Big-O? explica isso.