Aplanar una lista anidada
La misión
Problema
Recibes una lista cuyos elementos son enteros u otras listas, anidadas a cualquier profundidad. Devuelve una sola lista plana con todos los enteros en el orden en que aparecen al leer la estructura de izquierda a derecha. Las listas vacías no aportan nada.
Ejemplos
Input: items = [1, [2, [3, 4]], 5]
Output: [1, 2, 3, 4, 5]
Por qué: la profundidad no cambia el orden de lectura
Input: items = [[], [[]], [1]]
Output: [1]
Por qué: las listas vacías desaparecen a cualquier profundidad
Input: items = []
Output: []
Por qué: caso límite: no hay nada que leer
Pistas
0 / 3
Mira un solo elemento en lugar de toda la estructura. Solo hay dos tipos de elemento, y uno de ellos es fácil.
Una lista anidada es el mismo problema en miniatura. La función que resuelve la lista externa ya resuelve la interna.
Recorre los elementos una vez. Agrega un entero directamente al resultado; para una lista, llama a la función sobre ella y extiende el resultado con lo que devuelve. La lista vacía es el caso base natural.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- items are integers or lists, nested to any depth
Solución
Cada elemento es o un valor que hay que conservar o una copia más pequeña del mismo problema, que es exactamente la forma para la que existe la recursión. Recorrer los elementos en orden conserva el orden de lectura, y extender con el subresultado hace que el anidamiento no se note en la salida. La lista vacía no necesita un caso especial: el bucle simplemente nunca se ejecuta. Cada entero y cada nodo de lista se visita una vez, así que el tiempo es O(n) en el número total de nodos, y la pila de llamadas (call stack) llega tan hondo como el anidamiento.
def flatten(items):
flat = []
for item in items:
if isinstance(item, list):
flat.extend(flatten(item)) # a nested list is a smaller problem
else:
flat.append(item)
return flat
print(flatten([1, [2, [3, 4]], 5])) # -> [1, 2, 3, 4, 5]
print(flatten([[], [[]], [1]])) # -> [1]
print(flatten([])) # -> []¿Lo que te frena es la idea y no el código? Fundamentos de la recursión lo explica.