通过移动字母来复制数组中的零以腾出空间

Question

我正在解决一个需要以下输入的问题：[1, 0, 2, 3, 0, 4, 5, 0]并输出这个：[1, 0, 0, 2, 3, 0, 0, 4]我的函数检测零，当零是列表的第 i 个元素时，它i+1也变成零，并且列表的其余部分被移动以为其腾出空间。列表末尾的元素被推出以腾出空间。我能够用两个for循环来完成它，但是它有O(n^2)，我想在 中完成它O(n)。我想出了这个：new = [0] * len(arr)zeroes = 0d = 0我创建第二个零列表，zeroes对零列表进行计数，并且d是要复制第二个列表的索引。我使用的数组是函数的输入，名为arr.首先我数零：for i in range(len(arr)):    if arr[i] == 0:        zeroes+=1  然后我复制。我通过索引检查该值是否为零，如果是，则跳过第 d 个和第 d+1 个元素。for i in range(len(arr)-zeroes):    if arr[i] == 0:        d+=1    else:        new[d] = arr[i]    d+=1然而对于：[1, 0, 2, 3, 0, 4, 5, 0]输出是：[1, 0, 0, 2, 3, 0, 0, 0]我不确定为什么最后一个元素没有改变。

Answer 1

这是一个更简单的解决方案，仍然是 O(n)：

a = [1,0,2,3,0,4,5,0]

b = []

for i in a:

    b.append(i)

    if i == 0:

        b.append(0)

b = b[:len(a)]

b 的值是

[1, 0, 0, 2, 3, 0, 0, 4]