Valores comunes de dos listas
La misión
Problema
Dadas dos listas de valores, devuelve los valores que aparecen en ambas. Cada valor común aparece una sola vez en el resultado aunque alguna de las listas lo repita, y el resultado sigue el orden en que los valores aparecen por primera vez en la primera lista.
Ejemplos
Input: a = [1, 2, 2, 1], b = [2, 2]
Output: [2]
Por qué: un valor común aparece una sola vez, sin importar cuántas veces se repita
Input: a = [4, 9, 5], b = [9, 4, 9, 8, 4]
Output: [4, 9]
Por qué: el orden viene de la primera lista, no de la segunda
Input: a = [1, 2], b = [3]
Output: []
Por qué: caso límite: las listas no tienen nada en común
Pistas
0 / 3
Comparar cada valor de la primera lista con toda la segunda da la respuesta correcta, pero relee demasiado. Pregúntate qué podrías preparar una sola vez, antes de empezar a comparar.
La pregunta que se hace en cada elemento de la primera lista es una prueba de pertenencia en la segunda lista, y hay una estructura cuyo único trabajo es responder eso en tiempo constante.
Carga la segunda lista en un conjunto. Recorre la primera lista una vez y quédate con un valor cuando el conjunto lo contenga y todavía no lo hayas agregado al resultado. Lleva lo que ya agregaste en un segundo conjunto, para que los duplicados de la primera lista no produzcan una salida duplicada.
- Tiempo objetivo
- O(n + m)
- Espacio objetivo
- O(m)
Solución
Cargar la segunda lista en un conjunto convierte cada una de las n comparaciones en una búsqueda en tiempo constante en lugar de un recorrido. Recorrer la primera lista en orden hace que el orden de la salida salga sin costo, y un segundo conjunto de valores ya agregados deja fuera las repeticiones sin ordenar ni posprocesar. El tiempo es O(n + m) en promedio, y el espacio es O(m) para el conjunto de búsqueda más los valores agregados.
def shared_values(a, b):
pool = set(b) # membership in b is now a constant-time test
out, reported = [], set()
for x in a:
if x in pool and x not in reported:
out.append(x) # first appearance in a fixes the order
reported.add(x)
return out
print(shared_values([1, 2, 2, 1], [2, 2])) # -> [2]
print(shared_values([4, 9, 5], [9, 4, 9, 8, 4])) # -> [4, 9]
print(shared_values([1, 2], [3])) # -> []¿Lo que te frena es la idea y no el código? Fundamentos de la tabla hash lo explica.