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]
 

提示：

1 <= arr.length <= 10000
0 <= arr[i] <= 9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/duplicate-zeros

 

代码如下：

时间复杂度O(n)，空间复杂度O(1)。

func duplicateZeros(_ arr: inout [Int]) {
        // 数组为空 或 只有1个元素时，直接返回
        if arr.count < 2 {
            return
        }
        
       // 本次遍历目的：找出可复写0的个数
        var i = 0, j = 0
        while j < arr.count {
            if arr[i] == 0 {
                j += 1
            }
            i += 1
            j += 1
        }
        
        // 没有元素为0；
        if i == j {
            return
        }
        // 当且仅当最后一个元素为0 
        else if i == arr.count-1 && j > arr.count {
            return
        }
        
        // i,j回到下次遍历的开始位置
        i -= 1
        j -= 1
        while i >= 0 {
            if j < arr.count {
                arr[j] = arr[i]
            }
            if arr[i] == 0 {
                j -= 1
                arr[j] = arr[i]
            }
            
            i -= 1
            j -= 1
        }
    }