LeetCode.1089-重复的0(Duplicate Zeros)

这是小川的第392次更新，第423篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第255题（顺位题号是1089）。给定一个固定长度的整数数组arr，复制每次出现的零，将剩余的元素向右移动。

请注意，不会写入超出原始数组长度的元素。

对输入数组进行上述修改，不要从函数返回任何内容。

例如：

输入：[1,0,2,3,0,4,5,0]

输出：null

说明：调用函数后，输入数组被修改为：[1,0,0,2,3,0,0,4]

输入：[1,2,3]

输出：null

说明：调用函数后，输入数组被修改为：[1,2,3]

注意：

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

02 第一种解法

新建一个List，遍历arr中的元素，如果为0，添加两次到List中，然后将List中的前n个元素回写到arr中，n为arr的长度。

public void duplicateZeros(int[] arr) {

    List<Integer> list = new ArrayList<Integer>();

    for (int num : arr) {

        if (num == 0) {

            list.add(0);

        }

        list.add(num);

    }

    for (int i=0; i<arr.length; i++) {

        arr[i] = list.get(i);

    }

}

03 第二种解法

我们也可以不使用List，将arr复制一份出来，创建一个索引，遍历复制数组，将元素回写到arr中，遇到0就重复赋值一次。

public void duplicateZeros2(int[] arr) {

    int n = arr.length, index = 0;

    int[] copy = arr.clone();

    for (int num : copy) {

        if (index >= n) {

            break;

        }

        if (index+1 < n && num == 0) {

            arr[index++] = 0;

            arr[index++] = 0;

        } else {

            arr[index++] = num;

        }

    }

}

04 第三种解法

我们也可以不使用额外的空间，通过双指针来实现。

先遍历arr，统计其中元素值为0的元素个数，记为count，从后往前遍历，一个长度为arr的长度，另外一个长度为arr的长度加count，遇到0就重复回写一次。

public void duplicateZeros3(int[] arr) {

    int count = 0;

    for (int num : arr) {

        if (num == 0) {

            count++;

        }

    }

    int n = arr.length, n2 = n + count;

    // i是原数组的索引，j是原数组的长度加count

    for (int i=n-1, j= n2-1; i < j; i--, j--) {

        if (arr[i] != 0) {

            if (j < n) {

                arr[j] = arr[i];

            }

        } else {

            // 遇到0，再重复一次

            if (j < n) {

                arr[j] = arr[i];

            }

            j--;

            if (j < n) {

                arr[j] = arr[i];

            }

        }

    }

}

05 小结

算法专题目前已连续日更超过八个月，算法题文章261+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

巴特西