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

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 = 0

d = 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]