如何在Python中以O(N)复杂度原地移除列表中符合谓词的元素？

问题 #

如何**原地（IN-PLACE）**移除列表中所有符合谓词的元素，且算法时间复杂度必须是O(N)，不能是O(N²)？

测试代码框架如下：

from typing import TypeVar, Callable

T = TypeVar("T")

def remove_if(a: list[T], predicate: Callable[[T], bool]):
    # 请实现这里的逻辑

# 测试用例
a = [1, 2, 3, 4, 5]
remove_if(a, lambda x: x % 2 == 0)
assert(a == [1, 3, 5])

注：Rust中有Vec::retain()、C++中有std::remove_if()（需搭配erase()）实现类似功能，Python中有没有等价的实现？

实现方案 #

用双指针（快慢指针）的思路可以高效完成原地修改，时间复杂度O(N)：

from typing import TypeVar, Callable

T = TypeVar("T")

def remove_if(a: list[T], predicate: Callable[[T], bool]):
    slow = 0
    for fast in range(len(a)):
        # 保留不符合移除条件的元素
        if not predicate(a[fast]):
            a[slow] = a[fast]
            slow += 1
    # 截断列表，只保留需要的部分
    del a[slow:]

逻辑说明 #

• 快指针遍历所有元素，慢指针标记下一个要保留元素的存放位置
• 遇到不需要移除的元素时，将其复制到慢指针位置，慢指针向前移动一位
• 遍历结束后，删除慢指针之后的所有元素，完成原地修改
• 全程仅遍历列表一次，无额外大空间开销，严格符合O(N)时间复杂度要求

Python里的等价实现 #

Python标准库没有直接对应Vec::retain或std::remove_if的原生方法，但可以用切片赋值快速实现类似的原地效果：

a = [1,2,3,4,5]
# 原地替换列表内容，保留奇数
a[:] = (x for x in a if x % 2 != 0)
assert(a == [1,3,5])

不过这种方式本质是生成临时迭代器后替换原列表内容；如果追求极致空间效率，双指针实现更优——它完全在原列表内存空间上操作，不需要额外临时存储。

内容的提问来源于stack exchange，提问作者Timmmm