时间戳

首页 > 解决方案 > 将所有零值移到数组的末尾

python - 将所有零值移到数组的末尾

问题描述

如何在python中编写代码将所有零值移到数组的末尾（有一个包含正值列表（大于0）的恒定大小整数数组。数据之间也有一些零值）。

示例数组 [ 5 ,10, 0, 4, 0, 8, 0, 3 ]

我试过这种方式，但它重复了3

    x=[5,10,0,4,0,8,0,3]
for i in range(1,8):
    if x[i]==0:
        for j in range(i,8):
            x[j]=x[j+1]

for i in range(0,8):
    print(x[i] )

标签： pythonalgorithmdata-structures

解决方案

这是荷兰国旗问题的简化版本，您尝试将数组划分为 3 个不同的部分，而不是此处的 2 个。

解决这个问题的方法是使用两指针技术。一个指针A表示它后面的所有元素肯定是非零，而另一个指针B向前移动以寻找非零。每当B找到非零时，它就会将该元素与索引处的元素交换A并A递增。这导致所有非零元素落在末尾的左侧A和右侧的所有零。A

def partition_zero_nonzero(arr): 
    l = 0   
    for i, el in enumerate(arr): 
        if el != 0: 
            arr[l], arr[i] = arr[i], arr[l]  
            l += 1  
    return arr

快速测试：

arr =  [ 5 ,10, 0, 4, 0, 8, 0, 3 ]
partition_zero_nonzero(arr)
[5, 10, 4, 8, 3, 0, 0, 0]

请注意，此方法还尊重原始数组的相对顺序。

当然，也可以通过使用额外的空间来解决这个问题，将所有非零元素添加到新数组中并用零填充其余元素。

更新：由于您发布了一个具有二次时间复杂度的解决方案并询问它是否正确。这是您更正的解决方案。我重申它确实效率不高，你可以做得更好，但它可以用于教育目的。

def partition_zero_nonzero_quadratic(arr): 
    n_zeros = 0 
    for i in range(len(arr)): 
        if arr[i] == 0: 
            for j in range(i, len(arr)-1): 
                arr[j] = arr[j+1] 
            n_zeros += 1 
    for i in range(len(arr)-n_zeros, len(arr)): 
        arr[i] = 0 
    return arr

小测试：

arr = [ 5 ,10, 0, 4, 0, 8, 0, 3 ]
partition_zero_nonzero_quadratic(arr)
[5, 10, 4, 8, 3, 0, 0, 0]

推荐阅读