Leetcode 1089. 复写零

题目描述

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。

要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1:

输入：[1,0,2,3,0,4,5,0] 输出：null 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2:

输入：[1,2,3] 输出：null 解释：调用函数后，输入的数组将被修改为：[1,2,3]

解法

由描述可知，该题目要求在数组中的每个零后添加一个零，原零后数组元素右移一位。

最简单方式自然是遍历数组元素，每遇到一个零，将后续所有元素右移一位，填入零元素，直至数组末尾。但是该方式下，一个元素可能存在多次重复移动的操作，如果能直接确定每一个元素的最终位置，一次将元素移动到最终位置的话，则执行上较为高效。

由题目可知，每个元素的最终位置为，当前元素位置加上该元素前零的个数。所以不妨计算出元素前零的个数，则可以直接一次将元素移动到最终位置上。

在遍历数组计算零的个数时，不一定遍历到数组末尾，因为数组中若存在零，则必然有元素被移除数组； 需要注意下，如果最后一个元素是零的话，需要判断复写该零值，是否超出数组边界。

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        count,i=0,0
        while i+count<len(arr):
            if arr[i]==0:
                count+=1
            i+=1
        i-=1
        if i+count==len(arr):
            arr[-1],count,i=0,count-1,i-1
        while i>=0 and count>0:
            arr[i+count]=arr[i]
            if arr[i]==0:
                count-=1
                arr[i+count]=0
            i-=1