Verificar valores repetidos
A missão
Problema
Dada uma lista de valores, decida se algum valor aparece mais de uma vez. Retorne verdadeiro se pelo menos um valor se repetir em qualquer ponto da lista, e falso quando todos os valores forem únicos. As repetições não precisam estar lado a lado.
Exemplos
Input: items = [4, 1, 9, 1]
Output: True
Por quê: o valor 1 aparece em duas posições diferentes
Input: items = [4, 1, 9]
Output: False
Por quê: os três valores são diferentes
Input: items = []
Output: False
Por quê: edge case: uma lista vazia não pode conter repetição
Dicas
0 / 3
Comparar cada par responde à pergunta, mas dá muito mais trabalho do que o necessário. Pense no que você anotaria enquanto lê a lista uma única vez.
A única pergunta em cada elemento é se você já encontrou aquele valor antes, o que é um teste de pertencimento, e não uma busca.
Mantenha uma coleção dos valores já vistos. Para cada elemento, verifique primeiro o pertencimento e pare imediatamente com resposta positiva se ele estiver lá; caso contrário, adicione-o e continue. Chegar ao fim significa que tudo era único.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
Um conjunto (set) de valores já vistos transforma a pergunta sobre valores repetidos em um teste de pertencimento em tempo constante. Percorrer a lista uma vez e testar antes de inserir faz a resposta ser retornada no instante em que aparece uma segunda cópia, sem terminar a varredura. O tempo é O(n) em média, e o espaço é O(n) no pior caso, quando todos os valores são distintos.
def has_repeat(items):
seen = set() # values met so far
for x in items:
if x in seen: # this exact value already appeared
return True
seen.add(x)
return False # the scan finished without a collision
print(has_repeat([4, 1, 9, 1])) # -> True
print(has_repeat([4, 1, 9])) # -> False
print(has_repeat([])) # -> FalseTravou na ideia, e não no código? Contagem de frequência explica isso.