Início / coding / Perguntas / 79251266
Accepted
ariko stephen
Asked: 2024-12-04 21:06:09 +0800 CST

Complexidade de espaço e tempo de achatamento de uma lista aninhada de profundidade arbitrária

  • 772

Dada uma lista Python que contém listas aninhadas de níveis arbitrários de aninhamento, o objetivo é retornar uma lista completamente simplificada, ou seja, para a entrada de exemplo [1, [2], [[[3]]], 1], a saída deve ser [1, 2, 3, 1].

Minha solução:

def flatten(lst):
  stack = [[lst, 0]]
  result = []

  while stack:
    current_lst, start_index = stack[-1]
    for i in range(start_index, len(current_lst)):
      if isinstance(current_lst[i], list):
        # Update the start_index of current list
        # to the next element after the nested list
        stack[-1][1] = i + 1
        # Add nested list to stack
        # and initialize its start_index to 0
        stack.append([current_lst[i], 0])
        # Pause current_lst traversal
        break
      # non list item
      # add item to result
      result.append(current_lst[i])
    else:
      # no nested list
      # remove current list from stack
      stack.pop()

  return result

Gostaria de saber a complexidade de tempo e espaço (espaço auxiliar) da minha solução, se estiver correta.

O que eu penso

Complexidade de tempo:

Acredito que a solução tem uma complexidade de tempo de O(m + n), onde m é o número total de listas aninhadas em todos os níveis e n é o número total de elementos atômicos em todos os níveis (elementos não listados).

Complexidade do Espaço:

Acredito que a complexidade do espaço é O(d) , onde d é a profundidade da lista mais aninhada. Isso ocorre porque a pilha rastreia o estado atual da travessia, e seu tamanho é proporcional à profundidade de aninhamento

A solução está correta?

A análise de tempo e espaço está correta?

python

1 respostas

  1. Best Answer

    Sim, a solução está correta.

    Sim, a análise de tempo e espaço está correta... se você não contar o espaço usado por resultcomo espaço auxiliar, o que é razoável. Embora note que resultoveraloca/realoca, o que você poderia considerar como tomar O(n) espaço auxiliar. Você poderia otimizar isso fazendo duas passagens sobre toda a entrada, uma para contar os elementos atômicos, então criar result = [None] * n, e então outra passagem para preenchê-lo.

    A propósito, é melhor usar iteradores em vez de seus próprios pares lista+índice ( tente isso online! ):

    def flatten(lst):
  stack = [iter(lst)]
  result = []
  while stack:
    for item in stack[-1]:
      if isinstance(item, list):
        stack.append(iter(item))
        break
      result.append(item)
    else:
      stack.pop()
  return result

    Ou com a otimização de espaço mencionada ( Tente isso online! ):

    def flatten(lst):
  def atoms():
    stack = [iter(lst)]
    while stack:
      for item in stack[-1]:
        if isinstance(item, list):
          stack.append(iter(item))
          break
        yield item
      else:
        stack.pop()
  n = sum(1 for _ in atoms())
  result = [None] * n
  i = 0
  for result[i] in atoms():
    i += 1
  return result
    • 1

relate perguntas