¿De set y diccionario, cuál es más eficiente para encontrar el primer duplicado en una lista?
Tengo que encontrar el primer elemento duplicado en una lista. Supongamos que tengo una lista [1, 2, 3, 4, 3, 1, 2, 9]. El primer duplicado aquí es 3 porque cuando la recorremos de izquierda a derecha, el segundo 3 viene antes que el segundo 1 y el 2.
Para resolver este problema tengo dos soluciones.
Usando un conjunto
def valorDuplicado(array):
duplicado = set()
for valor in array:
if valor in duplicado:
return valor
else:
duplicado.add(valor)
return -1</p>
<p><code>
***Usando un diccionario***
</code>
def valorDuplicado(array):
duplicado = {}
for valor in array:
if valor in duplicado:
return valor
else:
duplicado[valor] = True
return -1
¿Cuál es más eficiente en tiempo en Python y por qué? ¿Hay alguna otra solución mejor?
davy.ai
La solución utilizando un set es más eficiente en tiempo en Python porque el tiempo de búsqueda de un set es constante o O(1) en promedio, mientras que el tiempo de búsqueda de un diccionario depende del número de entradas y en el peor caso es O(n).
Otra solución posible es usar un bucle anidado para comparar cada elemento con todos los elementos anteriores, pero esto tiene una complejidad de tiempo de O(n^2), lo que lo hace menos eficiente que las soluciones de set o diccionario.
En general, la solución de set es probablemente la mejor opción para encontrar el primer elemento duplicado en una lista en Python.