在Python中remove()将删除列表中第一个出现的值。

如何从列表中删除一个值的所有出现?

这就是我的想法:

>>> remove_values_from_list([1, 2, 3, 4, 2, 2, 3], 2)
[1, 3, 4, 3]

当前回答

没有人给出时间和空间复杂性的最佳答案,所以我想试试。下面是一种解决方案,它可以在不创建新数组的情况下删除所有特定值的出现,并且具有有效的时间复杂度。缺点是元素不能维持秩序。

时间复杂度:O(n) 额外空间复杂度:O(1)

def main():
    test_case([1, 2, 3, 4, 2, 2, 3], 2)     # [1, 3, 3, 4]
    test_case([3, 3, 3], 3)                 # []
    test_case([1, 1, 1], 3)                 # [1, 1, 1]


def test_case(test_val, remove_val):
    remove_element_in_place(test_val, remove_val)
    print(test_val)


def remove_element_in_place(my_list, remove_value):
    length_my_list = len(my_list)
    swap_idx = length_my_list - 1

    for idx in range(length_my_list - 1, -1, -1):
        if my_list[idx] == remove_value:
            my_list[idx], my_list[swap_idx] = my_list[swap_idx], my_list[idx]
            swap_idx -= 1

    for pop_idx in range(length_my_list - swap_idx - 1):
        my_list.pop() # O(1) operation


if __name__ == '__main__':
    main()

其他回答

如果你不关心列表的顺序,如果你关心最终的顺序,我相信这可能比其他任何方法都快。

category_ids.sort()
ones_last_index = category_ids.count('1')
del category_ids[0:ones_last_index]

以可读性为代价,我认为这个版本稍微快一点,因为它不强迫while重新检查列表,因此做完全相同的工作删除必须做的事情:

x = [1, 2, 3, 4, 2, 2, 3]
def remove_values_from_list(the_list, val):
    for i in range(the_list.count(val)):
        the_list.remove(val)

remove_values_from_list(x, 2)

print(x)

我们也可以使用del或pop来进行就地删除:

import random

def remove_values_from_list(lst, target):
    if type(lst) != list:
        return lst

    i = 0
    while i < len(lst):
        if lst[i] == target:
            lst.pop(i)  # length decreased by 1 already
        else:
            i += 1

    return lst

remove_values_from_list(None, 2)
remove_values_from_list([], 2)
remove_values_from_list([1, 2, 3, 4, 2, 2, 3], 2)
lst = remove_values_from_list([random.randrange(0, 10) for x in range(1000000)], 2)
print(len(lst))


现在说说效率:

In [21]: %timeit -n1 -r1 x = random.randrange(0,10)
1 loop, best of 1: 43.5 us per loop

In [22]: %timeit -n1 -r1 lst = [random.randrange(0, 10) for x in range(1000000)]
g1 loop, best of 1: 660 ms per loop

In [23]: %timeit -n1 -r1 lst = remove_values_from_list([random.randrange(0, 10) for x in range(1000000)]
    ...: , random.randrange(0,10))
1 loop, best of 1: 11.5 s per loop

In [27]: %timeit -n1 -r1 x = random.randrange(0,10); lst = [a for a in [random.randrange(0, 10) for x in
    ...:  range(1000000)] if x != a]
1 loop, best of 1: 710 ms per loop

正如我们所看到的,原地版本remove_values_from_list()不需要任何额外的内存,但它确实需要更多的时间来运行:

11秒的位置删除值 710毫秒用于列表推导,它在内存中分配一个新列表

没有人给出时间和空间复杂性的最佳答案,所以我想试试。下面是一种解决方案,它可以在不创建新数组的情况下删除所有特定值的出现,并且具有有效的时间复杂度。缺点是元素不能维持秩序。

时间复杂度:O(n) 额外空间复杂度:O(1)

def main():
    test_case([1, 2, 3, 4, 2, 2, 3], 2)     # [1, 3, 3, 4]
    test_case([3, 3, 3], 3)                 # []
    test_case([1, 1, 1], 3)                 # [1, 1, 1]


def test_case(test_val, remove_val):
    remove_element_in_place(test_val, remove_val)
    print(test_val)


def remove_element_in_place(my_list, remove_value):
    length_my_list = len(my_list)
    swap_idx = length_my_list - 1

    for idx in range(length_my_list - 1, -1, -1):
        if my_list[idx] == remove_value:
            my_list[idx], my_list[swap_idx] = my_list[swap_idx], my_list[idx]
            swap_idx -= 1

    for pop_idx in range(length_my_list - swap_idx - 1):
        my_list.pop() # O(1) operation


if __name__ == '__main__':
    main()

如果你没有内置过滤器,或者不想使用额外的空间,你需要一个线性解决方案……

def remove_all(A, v):
    k = 0
    n = len(A)
    for i in range(n):
        if A[i] !=  v:
            A[k] = A[i]
            k += 1

    A = A[:k]