关于我编写的“移零”递归代码的性能与实现方式咨询

问题背景 #

给定数组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()

1. 该代码是否为线性时间复杂度？ #

不是，你的递归解法时间复杂度为O(n²)，属于平方级时间复杂度。

原因在于：每次递归调用时，Min_Zero和Min_Not_Zero的while循环都会从指定位置开始扫描数组。最坏情况下（比如数组是[0,0,0,...,0,1]），每次扫描都要遍历接近整个数组的长度，而递归调用次数等于数组中零的个数（最多接近n次）。叠加后总操作次数会达到O(n²)级别，不符合线性时间O(n)的要求。另外，递归本身还会带来额外的栈空间开销。

2. 是否应改用双指针的常规写法？ #

非常建议改用双指针的常规写法，这种写法时间复杂度严格为O(n)（每个元素仅被遍历一次），空间复杂度为O(1)，逻辑更直观、代码更简洁，也没有递归的栈开销，完全符合题目要求。

双指针写法示例1（交换法）

def moveZeroes(nums):
    # slow指针指向当前需要放置非零元素的位置
    slow = 0
    # fast指针遍历整个数组寻找非零元素
    for fast in range(len(nums)):
        if nums[fast] != 0:
            # 交换快慢指针位置的元素
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    return nums

双指针写法示例2（填充法）

def moveZeroes(nums):
    slow = 0
    # 先将所有非零元素依次填充到数组前半部分
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    # 将slow指针之后的所有位置设为0
    for i in range(slow, len(nums)):
        nums[i] = 0
    return nums

这两种写法都能保证非零元素的相对顺序，且完全在原数组上修改。

内容的提问来源于stack exchange，提问作者Frederick Griffth