[LeetCode] 1089. Duplicate Zeros

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints:

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

复写零。

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

注意：请不要在超过该数组长度的位置写入元素。

要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/duplicate-zeros
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意不难理解，比较考验对追击型双指针的理解。

题目告诉我们在进行复写的时候，每次遇到一个0，就要在他的下一个位置再多写一个 0。如果正常从左往右操作就会造成原本0后面的数字会被覆盖，所以这里我们只能从右往左复写。

首先我们需要有两个指针 i，j，其中 i 只管往前走，遇到任何数字都只++一次；j 在遇到 0 的时候，再额外多走一步。这样，当 j 超出数组长度的时候，i 和 j 的间距就是我们要多添加多少个 0 的个数。之后我们再往回复写。注意由于此时 i 和 j 都在合法 index 的范围外，所以我们一开始要对两者都进行 -- 操作。为什么 i 也在范围外是因为第一次的 while 循环最后多走了一步。这里的不合法倒不是说越界，而是 i 多计算了一步。

当他们在合法的 index 范围内的时候，我们开始复写。我们判断，

当 j 在数组合法 index 范围内的时候，j 的位置上就无条件写上此时 arr[i] 的值

如果 arr[i] == 0 同时 --j >= 0 的话，arr[j] 和 arr[j--] 都要赋值成 0

时间O(n)

空间O(1) - 要求

Java实现

 1 class Solution {
 2     public void duplicateZeros(int[] arr) {
 3         // i和j之间的差距其实就是需要多少个额外的0
 4         // 在碰到0的时候j多走一步
 5         int i = 0;
 6         int j = 0;
 7         int len = arr.length;
 8         while (j < len) {
 9             if (arr[i] == 0) {
10                 j++;
11             }
12             i++;
13             j++;
14         }
15         
16         // 因为此时i, j都 == arr.length，其实是越界了所以要--
17         // 从右往左的时候，j负责把正确的数字写回数组
18         i--;
19         j--;
20         while (i >= 0) {
21             if (j < len) {
22                 arr[j] = arr[i];
23             }
24             if (arr[i] == 0 && --j >= 0) {
25                 arr[j] = 0;
26             }
27             i--;
28             j--;
29         }
30     }
31 }