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

Question

我想从数组中删除值x，我有以下约束：

1. 我只能穿过阵法一次
2. 不允许额外的内存/数据结构

所以

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

变成

^{pr2}$

只有一个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 removeSingleElement(value, array):
    """
    Remove value from the input array.
    Input parameters:
        value: Remove Value.
        array: Input array.
    Output parameters:
        return array.
    """
    #- Length of array.
    array_length = len(array)
    i = array_length - 1

    #- Iterate Array from higher index to Lower index.
    while i > -1:
        #- Check Current item value with remove value.
        if array[i] == value:
            #- Remove Value from the input list.
            array.pop(i)
            #- Append None value to input list.
            array.append(None)
        #- Decrement index value by 1
        i -= 1

    return array


remove_item = 'x'
input_array = ['x', 1, 2, 3, 'x', 4, 5, 'x']

output_array = removeSingleElement(remove_item, input_array)

print "Output:", output_array

输出：

^{pr2}$

Answer 2

假设允许您预先知道数组的长度并存储一个计数器，则可以执行以下操作：

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

Answer 3

你需要两个索引，一个用于阅读和写作：

def remove_element(value, array):
    reading_idx = writing_idx = 0
    while reading_idx < len(array):
        if array[reading_idx] != value:
            array[writing_idx] = array[reading_idx]
            writing_idx += 1
        reading_idx += 1
    while writing_idx < len(array):
        array[writing_idx] = None
        writing_idx += 1