leetcode 1089. 复写零

题目描述

1089. 复写零

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

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1：

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

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

提示：

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

解题思路

法1

指针

首先，统计数组中零的个数，记为 zerosCount。然后，计算复写后的数组长度，记为 newLength，即原始长度加上 zerosCount。

接下来，从数组的最后一个元素开始向前遍历。如果当前元素为零，将零复写到新数组的对应位置，并将 newLength 减1。然后，将当前元素复写到新数组的对应位置，并将 newLength 减1。

最终，数组 arr 就会被修改为复写零并向右平移的结果。

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func duplicateZeros(arr []int) {
    length := len(arr)
    zerosCount := 0
    
    // 统计数组中的零的个数
    for _, num := range arr {
        if num == 0 {
            zerosCount  
        }
    }
    
    // 计算复写后的数组长度
    newLength := length   zerosCount
    
    // 从后向前遍历数组，进行复写操作
    for i := length - 1; i >= 0; i-- {
        // 复写零
        if arr[i] == 0 {
            if newLength-1 < length {
                arr[newLength-1] = 0
            }
            newLength--
        }
        
        // 向右平移
        if newLength-1 < length {
            arr[newLength-1] = arr[i]
        }
        newLength--
    }
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 4 ms , 在所有 Go 提交中击败了 88.24% 的用户 内存消耗： 3.1 MB , 在所有 Go 提交中击败了 100.00% 的用户 通过测试用例： 30 / 30 炫耀一下: