我写的“找零”的递归代码怎么样？

Question

问题来了：

给定一个数组

nums

，编写一个函数，将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。 请注意，必须就地修改数组，而不创建数组的副本。

这段代码需要线性时间吗？如果不是，我应该使用两个指针以更正常的方式编写代码吗？

'''Recursively solve the 'Find Zero' problem without a new array created.'''

def Min_Zero(j, nums):
    while nums[j] != 0 and j < len(nums)-1:
        j += 1
    return j

def Min_Not_Zero(i, nums):
    while nums[i] == 0 and i < len(nums)-1:
        i += 1
    return i

# Swap the first zero element with the first non-zero element which is latter than the first zero element
def Swap_Zero(i=0, j=0, nums=[1, 2, 3, 4, 5, 0, 0, 0, 6, 0, 7, 0, 8, 0, 0, 9, 0, 0]):
    n = Min_Zero(j, nums)
    m = Min_Not_Zero(n, nums)
    if m < len(nums)-1 and n < len(nums)-1 and m > n:
        nums[m], nums[n] = nums[n], nums[m]
        Swap_Zero(m, n, nums = nums)
    return nums

Swap_Zero()

我已成功运行代码。已验证。

Answer 1

我们也可以用两个指针来完成

 arr = [2, 0, 1, 2,5]

l = 0
r = len(arr) - 1

while l < r:

    if (arr[l] == 0 and arr[r] != 0) :
        arr[l], arr[r] = arr[r], arr[l]
        l += 1
        r -= 1
    elif arr[l] != 0 and arr[r] == 0:
        l += 1
        r -= 1
    elif arr[l] != 0 and arr[r] != 0:
        l += 1