python - 在不使用额外内存的情况下就地从数组中删除值

Question

我想从数组中删除值 x 并且我有以下约束:

1. 我只能遍历一次数组
2. 不允许有额外的内存/数据结构

这样

a = [1, 2, 'x', 3, 4, 5]

成为

[1, 2, 3, 4, 5, None]

只有一个 x 的情况很简单，我只是将所有内容向左移动一位:

def removeSingleElement(value, array):
    i = 0
    while i < len(array)-1:
        if array[i] == value:
            for val in array[i:-1]:
                array[i] = array[i+1]
                i += 1 
        else:
            i += 1

    array[-1] = None
    return array

但是如何处理具有重复值的数组？

a = [1, 'x', 2, 3, 'x', 4]

应该变成

a = [1, 2, 3, 4, None, None]

(我的想法是我无法调整数组的大小，所以我想移动左边的所有内容并用 Null 的值填充其余部分)。

免责声明:这不是一个 Python 问题，我正在寻找通用算法，恰好我发现 Python 很方便表达这个想法；)

Answer 1

假设您可以提前知道数组的长度并存储一个计数器，则以下工作:

def remove_element(value,array):
    shift = 0
    for index in xrange(len(array)):
        try:
            array[index] = array[index + shift]
            while array[index] == value:
                shift += 1
                array[index] = array[index + shift]
        except IndexError:
            array[index] = None