复写零（双指针）

目录

一：题目链接

二：题目思路

三：代码实现

---

一：题目链接

        题目的要求是把数组中的为零元素复制一个，再依次按照原数组往后排序下去，直到原数组满了为止。

二：题目思路

        首先，我们要找到最后一个要复写的元素，可以利用双指针的思路，先定义一个 cur 指针，初始化为0，再定义一个 dest 指针，初始化为 -1 ；然后让 cur 往后遍历数组，遇到非零元素时，dest ++ ，cur 遇到零元素时， dest += 2 ，直到 dest 达到数组 .length - 1 的位置停止；注意，这会有一个特殊的情况，比如 [ 1 , 0 , 2  , 0 , 3 ] 这样的数组， cur 到达最后一个0位置的时候，dest 会 += 2 到达数组的 .length 的位置，也就是越界了，这种情况我们需要特殊处理。

        其次，当找到最后一个要复写的元素后，我们可以从后往前复写元素，当 cur 位置的元素非零时，cur 位置的元素覆盖 dest 位置的元素，然后 cur 和 dest 都减一；如果 cur 位置的元素为零时，dest 和 dest - 1 的位置复写为 0 ，然后 cur 和 dest 都减一。当然，上面说的一个特殊情况也就是[ 1 , 0 , 2  , 0 , 3 ] 这样的数组，dest位置在 .length 的位置，cur 在最后一个 0 的位置，那么为了迎合上面的处理流程，我们可以把 .length - 1 位置的元素改为0，cur-- ,  dest -=2 即可。

三：代码实现

        //找到第一个要复写的数的下标int cur = 0;int dest = -1;while(cur < arr.length) {if(arr[cur] != 0) {dest++;}else {dest+=2;}if(dest >= arr.length - 1) {break;}cur++;}//处理dest越界的情况if(dest == arr.length) {arr[arr.length - 1] = 0;cur--;dest-=2;}//从后往前复写while(cur >= 0) {if(arr[cur] == 0) {arr[dest] = 0;arr[--dest] = 0;}else {arr[dest] = arr[cur];}cur--;dest--;}