面试题：Python列表删除元素：复杂场景下的策略应用

Question

现有一个嵌套列表 `nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]`，要求删除其中所有值为偶数的元素。请编写代码实现，并说明选择这种删除策略（如遍历方式、使用的方法等）的原因，以及该策略在时间复杂度和空间复杂度上的表现。

Answer 1

nested_list = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for sublist in nested_list:
    i = 0
    while i < len(sublist):
        if sublist[i] % 2 == 0:
            sublist.pop(i)
        else:
            i += 1

print(nested_list)

选择该删除策略的原因

1. 遍历方式：使用嵌套循环来遍历嵌套列表。外层循环遍历每个子列表，内层循环遍历子列表中的每个元素。选择while循环是因为在删除元素时，列表的长度会发生变化，while循环能更好地适应这种动态变化，避免因索引问题导致错误。
2. 使用的方法：使用pop方法删除元素，直接在原列表上进行修改，操作简单直接。

时间复杂度

• 假设嵌套列表中总共有N个元素，最外层循环遍历子列表，每次内层循环遍历子列表中的元素。在最坏情况下，每次删除元素后，后续元素都需要向前移动，所以时间复杂度为$O(N^2)$。

空间复杂度

• 由于是在原列表上进行操作，没有使用额外的与输入规模相关的空间，所以空间复杂度为$O(1)$。