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

Question

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

我只能遍历一次数组
不允许额外的 memory/data 结构

所以

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]

（我的想法是我无法调整数组的大小，所以我想移动左侧的所有内容并用 Nulls 值填充其余部分）。

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

Answer 1

您需要两个索引，一个用于读取，一个用于写入：

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

Answer 2

这可能是作弊，但是...

def remove(value, array):
    try:
        while True:
            del(array[array.index(value)])
            array.append(None)
    except ValueError:
        pass

    return array

Answer 3

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

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 4

代码：

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

输出：

vivek@vivek:~/Desktop/Whosebug$ python remove_item.py 
Output: [1, 2, 3, 4, 5, None, None, None]

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

Remove values from an array in-place without using extra memory

python

arrays

algorithm

dynamic-arrays