1089. 复写零『简单』

题目来源于力扣（LeetCode）

目录

• 一、题目
• 二、解题思路
• 三、代码实现
• 四、执行用时
• 五、部分测试用例

一、题目

1089. 复写零

题目相关标签：数组

说明：

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

二、解题思路

1. 遍历 arr 数组，记录下数字 0 出现的次数，如当前索引加 1 再加数字 0 出现的次数大于等于 arr 数组长度时，结束循环

2. 此时变量 i 的值就相当于新数组的结束索引，arr 数组中索引 i 后的元素将被替换

3. 倒序遍历 arr 数组，将索引 i 上的元素依次为数组元素，当索引 i 上的元素为 0 时，则进行复写，即将其前 1 位元素也赋值为 0

注意点：

1. 题目要求：从前往后开始复写，而代码中采用从后往前复写，则存在奇数个 0 时，替换时容易将 0 前的非 0 元素也替换为 0，那么这是错误的，需要进行逻辑控制

2. 如何逻辑控制，保证复写 0 时不将非 0 元素也替换掉？

   zero + i <= arr.length - 1)，仅当前元素为 0 且索引 i 加上元素 0 的个数小于等于 arr 数组的最大索引时，才能将其前一位元素替换为 0，完美避免了，奇数个 0 时的复写情况

三、代码实现

public static void duplicateZeros(int[] arr) {
    // 定义变量 i 作为数组的长度
    int i = 0;
    // 变量 zero 等于多少则表示数组将超过的元素
    int zero = 0;

    for (; i < arr.length; i++) {
        if (arr[i] == 0) {
            zero ++;
        }
        // 记录下索引 i
        if (zero + (i + 1) >= arr.length) {
            break;
        }
    }
    // 数组中没有元素 0 时，return
    if (zero == 0) {
        return;
    }
    // 从后往前遍历，遇到元素 0 时，使其前一位也为 0
    for (int j = arr.length - 1; j > 0; j --) {
        // 数组的最后位等于数组索引 i 上的元素
        arr[j] = arr[i];
        // 当前遍历元素为 0，且零的个数加 i 小于等于数组长度减 1
        // int[] arr = {8, 4, 5, 0, 0, 0};  // change:{8, 4, 5, 0, 0, 0} 的情况
        // int[] arr = {8, 4, 5, 0, 0, 0, 0, 7};  // change:{8, 4, 5, 0, 0, 0, 0, 0}
        if (arr[j] == 0 && (zero + i <= arr.length - 1)) {
            // 使其前一位元素也为 0
            arr[j - 1] = 0;
            // 索引 j 再次减 1，
            j --;
        }
        // 索引 i 也往前走
        i--;
    }
}

四、执行用时

五、部分测试用例

public static void main(String[] args) {
//    int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};  // change to:{1, 0, 0, 2, 3, 0, 0, 4}
//    int[] arr = {1, 2, 3};  // change to:{1, 2, 3}
    int[] arr = {8, 4, 5, 0, 0, 0, 0, 0};  // change to:{8, 4, 5, 0, 0, 0, 0, 0}
    duplicateZeros(arr);
    System.out.println(Arrays.toString(result));
}