Comprobar valores repetidos
La misión
Problema
Dada una lista de valores, decide si algún valor aparece más de una vez. Devuelve verdadero si al menos un valor se repite en cualquier parte de la lista, y falso cuando todos los valores son únicos. Las repeticiones no tienen que estar una al lado de la otra.
Ejemplos
Input: items = [4, 1, 9, 1]
Output: True
Por qué: el valor 1 aparece en dos posiciones distintas
Input: items = [4, 1, 9]
Output: False
Por qué: los tres valores son distintos
Input: items = []
Output: False
Por qué: caso límite: una lista vacía no puede contener una repetición
Pistas
0 / 3
Comparar cada par responde la pregunta, pero hace mucho más trabajo del necesario. Piensa en qué anotarías mientras lees la lista una sola vez.
La única pregunta en cada elemento es si ya viste ese valor antes, y eso es una prueba de pertenencia, no una búsqueda.
Mantén una colección de los valores ya vistos. Para cada elemento, primero comprueba si ya está en ella y, si está, detente de inmediato con una respuesta positiva; si no, agrégalo y sigue. Llegar al final significa que todo era único.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Solución
Un conjunto de valores ya vistos convierte la pregunta del valor repetido en una prueba de pertenencia en tiempo constante. Recorrer la lista una vez y comprobar antes de insertar significa que la respuesta se devuelve en cuanto aparece una segunda copia, sin terminar el recorrido. El tiempo es O(n) en promedio, y el espacio es O(n) en el peor caso, cuando todos los valores son 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([])) # -> False¿Lo que te frena es la idea y no el código? Conteo de frecuencias lo explica.