python - 在线性时间内从列表中删除所有出现的值

Question

我想在 python 中实现一个程序，其中在线性时间 (O(n)) 内从列表中删除所有出现的值。已经有类似的问题的帖子，但没有人有在线性时间内完成它的限制。

我设法想出了一个解决方案，但我正在寻找一个更简单、更清晰的版本(或者最好是一个完全不同的实现)。

下面我使用前后两个“指针”来遍历列表。两者都从 0 开始并遍历列表，直到它们达到我们想要删除的值。在那一点上，前面的指针检查后面的整数是否也是我们要删除的值。前端指针继续遍历，直到我们命中第一个整数，这不是我们想要的值。然后我交换值(value)并继续这个过程。

def remove_all(lst, val):
    back = 0
    front = 0
    while (front < len(lst)-1):
        while(front < len(lst) and lst[front] != val):
            front += 1
            back += 1
        if (front < len(lst)-1 and lst[front] == val):
            while(front < len(lst)-1 and lst[front] == val):
                front += 1
            lst[back], lst[front] = lst[front], lst[back]
            back += 1
    if (lst[-1] != val):
        raise ValueError('Value not present in the list')
    while(len(lst) != 0 and lst[-1] == val):
        lst.pop()

Answer 1

我不确定你在做什么，但你把它复杂化了。有两种方法。

选项 1
返回一个新列表。这可以通过列表组合或循环来完成。

def remove_all(lst, val):
    return [x for x in lst if x != val]

或者，

def remove_all_gen(lst, val):
    for i in lst:
        if i != val:
            yield i

print(list(remove_all([1, 1, 2, 2, 3, 1, 2], 1)))
[2, 2, 3, 2]

这两个解都是线性的。

---

选项 2
要就地修改列表，您可以使用 del 反向迭代。

def remove_all(lst, val):
   for i in range(len(lst) - 1, -1, -1):
       if lst[i] == val:
          del lst[i]

l = [1, 1, 2, 2, 3, 1, 2]
remove_all(l, 1)

print(l)
[2, 2, 3, 2]

虽然此解决方案就地修改了列表，但它不再是线性的(感谢注释)，因为 del 是线性操作，需要移动元素。

作为一种良好做法，如果您正在执行就地变更，请不要从函数返回任何内容。