【刷题日记】1089. 复写零
本次刷题日记的第 68 篇，力扣题为：1089. 复写零，简单
一、题目描述：
复写零，这真是一个简单题吗？看我们能复写多少个零
二、这道题考察了什么思想？你的思路是什么？
复写零，都给我们提示了哪些信息：
- 题目给出了我们 1 个数组，数组中元素都是无序的整型数字
- 题目要求我们在数组中找到所有的
0并且将它在相邻位置 copy 一份，其余的元素顺势向后移一位
- 题目还有一个要求就是，要求我们在原有数组上进行处理，不能引入额外的数组，且题目给出的函数是没有返回值的
分析
看到这里，其实我们就直接大小那种需要开辟一个 help 数组，来进行偷龙转凤，然后 copy 给原数组的方式，这个方式在这个题，就不符合题意了
那我们好好思考一下，如何如处理会比较好呢，暂时来看有 3 个办法：
- 第一种，咱们遍历数组，当有遇到
0，就把他后面的元素全部往后推 1 为，并在当前0后面的元素也赋值为0，这种方式时间复杂度为高一些
- 第二种，咱们直接将整型数组，通过库函数，转成字符串，将
0替换成00，最后，按照题目给出数组来截取字符串的前 n 个数字，赋值给到原有数组，这种方式，空间复杂度为高一些
- 第三种，咱们可以使用双指针的方式，具体详情我们来分析和模拟一下
例如有这么一个源数组 [1,0,2,0,1]
| 索引 | 0 | 1 | 2 | 3 | 4 | 长度 n = 5 |
|---|---|---|---|---|---|---|
| 数值 | 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 之后的结果是
| 索引 | 0 | 1 | 2 | 3 | 4 | 长度 n = 5 |
|---|---|---|---|---|---|---|
| 数值 | 1 | 0 | 2 | 0 | 1 | |
| 结果 | 1 | 0 | 0 | 2 | 0 | 长度 n = 5 |
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
编码的时候需要注意，如果 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. 复写零
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是小魔童哪吒，欢迎点赞关注收藏，下次见~