主页 / coding / 问题 / 79251266
Accepted
ariko stephen
Asked: 2024-12-04 21:06:09 +0800 CST

展平任意深度嵌套列表的空间和时间复杂度

  • 772

给定一个包含任意嵌套级别的嵌套列表的 python 列表，目标是返回一个完全扁平的列表，即对于样本输入[1, [2], [[[3]]], 1]，输出应该是[1, 2, 3, 1]。

我的解决方案：

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

如果正确的话，我想知道我的解决方案的时间和空间复杂度（辅助空间）。

我的想法

时间复杂度：

我相信解决方案的时间复杂度为O（m + n），其中m是所有级别的嵌套列表的总数，n是所有级别的原子元素（非列表元素）的总数

空间复杂度：

我相信空间复杂度是O(d)，其中d是最嵌套列表的深度。这是因为堆栈跟踪遍历的当前状态，其大小与嵌套深度成正比

解决方案正确吗？

时间和空间的分析正确吗？

python

1 个回答

  1. Best Answer

    是的，解决方案是正确的。

    是的，时间和空间分析是正确的……如果你不将使用的空间算作result辅助空间，这是合理的。但请注意，result过度分配/重新分配，你可以认为这占用了 O(n) 辅助空间。你可以对整个输入进行两次传递来优化这一点，一次计数原子元素，然后创建result = [None] * n，然后另一次传递来填充它。

    顺便说一句，最好使用迭代器而不是自己的列表+索引对（在线尝试！）：

    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

    或者使用提到的空间优化（在线尝试！）：

    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

相关问题