往前
cur往前每走一步时dest也会跟一步当cur指向0时dest会指向cur前面一个而且把它变成零那这样cur前面永远都是零了。
既然往前遍历不行那今后呢?
今后
要思量 cur 和 dest 应该分别指向哪里。如果 cur 依然指向0,dest 指向-1,那和前向遍历是一样的,没有区别。但从标题中可以看到,输出结果的末了一个数字是4,而不是0。因此,我们可以将 cur 指向4的位置。cur 既然在前向遍历时指向第一个元素,那在后向遍历时指向输出结果的末了一个元素也是公道的。这样,cur 的位置已经确定了。那么 dest 应该指向哪里呢?
dest 是指向0照旧5,或者其他位置?这个位置不好判断。不妨直接开始遍历。当 cur 指向4时,dest 应该复写4的位置;当 cur 指向0时,dest 应该将4和5都复写为0。这样我们可以推断出 dest 的位置。
找末了一个被复写数的位置
我们希望找到复写后数组的末了一个元素,但直接继承今后遍历显然不行。尽管通过标题我们知道末了一个元素的值,但是遍历的竣事条件是什么呢?因此,我们必要改变计谋:从往前遍历转为使用“快慢指针”方法。
快指针比慢指针走得更快。当快指针到达数组的末尾或空位时,慢指针应该指向精确的位置。这样我们就可以确保通过快慢指针的方法定位到数组复写后指定的末了一个元素。
但是,必要注意的是,这种方法也是有限制的。具体来说,当 cur 指向0时,dest 必要往前走两步,而在其他情况下,dest 只必要往前走一步。
界限问题
在力扣上的标题只要是野指针就会报错,那在上面我们说过“当快指针到达数组的末尾或空位时”其中只要指针指向空位就会报错,那该如何办理呢?
当 cur 指向0时,如果剩下的空间不足2个位置,会导致 dest 出现越界。这时我们可以直接将末了一个位置修改为0。这背后的缘故起因是,如果空间不足两个位置,那末了一个位置必然是0,不然 dest 就不会越界。因此,我们可以放心地将其修改为0。
一旦末了一个位置被复写为0,意味着复写操纵已经完成。这时,cur 应该向前移动一位,dest 也必要向前移动。不过,由于复写0必要占用两个位置,以是 dest 应该减去2。
代码实现: