【刷题日记】1089. 复写零

本次刷题日记的第 68 篇，力扣题为：1089. 复写零，简单

一、题目描述：

复写零，这真是一个简单题吗？看我们能复写多少个零

二、这道题考察了什么思想？你的思路是什么？

复写零，都给我们提示了哪些信息：

• 题目给出了我们 1 个数组，数组中元素都是无序的整型数字
• 题目要求我们在数组中找到所有的0 并且将它在相邻位置 copy 一份，其余的元素顺势向后移一位
• 题目还有一个要求就是，要求我们在原有数组上进行处理，不能引入额外的数组，且题目给出的函数是没有返回值的

分析

看到这里，其实我们就直接大小那种需要开辟一个 help 数组，来进行偷龙转凤，然后 copy 给原数组的方式，这个方式在这个题，就不符合题意了

那我们好好思考一下，如何如处理会比较好呢，暂时来看有 3 个办法：

• 第一种，咱们遍历数组，当有遇到 0 ，就把他后面的元素全部往后推 1 为，并在当前 0 后面的元素也赋值为 0 ，这种方式时间复杂度为高一些
• 第二种，咱们直接将整型数组，通过库函数，转成字符串，将 0 替换成 00 ，最后，按照题目给出数组来截取字符串的前 n 个数字，赋值给到原有数组，这种方式，空间复杂度为高一些
• 第三种，咱们可以使用双指针的方式，具体详情我们来分析和模拟一下

例如有这么一个源数组 [1,0,2,0,1]

那么我们可以定义一个指针 i，和一个标识 top 当前已经装了多少个数字，例如当 i 对应的值为 非 0，则 top +1，当 i 对应的值为 0 ，则 top +2 ，因为咱们需要复写 0

遍历上述数组，当 i 为 3 的时候，top 大于或者等于 n 了， 如下：

就这么来看，我们知道了结果数组，都是索引 0 -- i 的数组，且其中的数字 0 还要被复写

那么接下来，就是咱们修改原数组数值的时候了，刚才说到是使用双指针，那么第 2 个指针现在就派上用场了

令 指针 j 等于数组的最后一个元素对应的索引，即 n-1 ，让 j 指针和 i 指针一起向左移动，i 指针上的值，赋值给 j 指针上的值，如果 i 指针上的值为 0 ，则 j 多向左跑 1 步，且也置为 0

另外，我们需要注意，当我们校验到此时的 top 是等于 n+1 的，那么说明，上述遍历到的情况，最后一个肯定是 0

既然上述遍历结束的最后一个元素是 0 ，那么意味着整个结果数组的最后一个元素也一定是 0

继续看图

那么 源数组 [1,0,2,0,1] 复写 0 之后的结果是

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码的时候需要注意，如果 top 校验到是 等于 n+1 的时候，一定是因为之前的第一遍遍历结束时候的最后一个元素为 0，此处需要特殊处理，即，结果数组中的最后一个元素也应是 0

编码如下：

func duplicateZeros(arr []int)  {
    n := len(arr)
    i := -1
    top := 0
    for top < n{
        i++
        if arr[i] == 0 {
            top += 2
        }else{
            top++
        }
    }
    // 如果 上述循环的最后一步是 top+= 2 退出的，那么就有这个情况
    j := n-1
    if top == n+1 {
        arr[j] = 0
        i--
        j--
    }
    for j > 0 {
        arr[j]  = arr[i]
        j--
        if arr[i] == 0 {
            arr[j] = 0
            j--
        }
        i--
    }
}

四、总结：

咱们这种解决方式的时间复杂度显而易见，为 O(n) ，咱们只是遍历了 2 遍题目给出的数组，并不是 O(n^2) 哦

空间复杂度是 O(1) ，这个也是非常明确的，咱们引入的是一些常数级别的变量占用空间资源

原题地址：1089. 复写零

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~