『LeetCode』1089 复写零

题目

1089. 复写零

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

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

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

示例 1：

输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：[1,2,3]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

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

题解

【复写零】『模拟』&『双指针』

模拟

最简单的思路就是另外开一个等大的数组，按要求将复写0后内容存入，最后复制回原数组。

# Code language: Python
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        st = [0 for _ in arr]
        i, j = 0, 0
        while i < n:
            st[i] = arr[j]
            if arr[j] == 0:
                i += 1
            i += 1
            j += 1
        for i in range(n):
            arr[i] = st[i]

// Code language: Java
class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int[] cp = arr.clone();
        for (int i = 0, j = 0; i < n; ++j) {
            cp[i++] = arr[j];
            if (arr[j] == 0 && i < n) cp[i++] = 0;
        }
        for (int i = 0; i < n; ++i) arr[i] = cp[i];
    }
}

// Code language: C++
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        vector<int> cp(arr);
        for (int i = 0, j = 0; i < n; ++j) {
            cp[i++] = arr[j];
            if (arr[j] == 0 && i < n) cp[i++] = 0;
        }
        for (int i = 0; i < n; ++i) arr[i] = cp[i];
    }
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(n)\)

双指针

实际上建立一个原数组的副本并不符合题目要求的“原地”，所以更好的办法是先找到复写后数组的右端点对应的值，在逆向的覆盖过去，覆盖回去的时候把 0 进行复写。

一种很好理解的方式就是把原数组当成一个原地的栈，先进行入栈操作（仅移动指针不修改），然后再进行出栈操作。

需要注意的是，右端点为 0 时这个 0 可能不需要复写（因为超出了数组范围），简单的例子是：

[1, 0]

这种情况需要跳过右端点元素。

# Code language: Python
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        idx, cnt = 0, 0
        while cnt < n:
            if arr[idx] == 0:
                cnt += 1
            idx += 1
            cnt += 1
        i, j = n - 1, idx - 1
        if arr[j] == 0 and cnt > n:
            arr[i] = 0
            i -= 1
            j -= 1
        while i > 0:
            arr[i] = arr[j]
            i -= 1
            if arr[j] == 0:
                arr[i] = 0
                i -= 1
            j -= 1

// Code language: Java
class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int i = n - 1, j = 0, cnt = 0;
        for ( ; cnt < n; ++j, ++cnt) {
            if (arr[j] == 0) ++cnt;
        }
        if (arr[--j] == 0 && cnt > n) {
            arr[i--] = 0;
            --j;
        }
        for (; i > 0; --j, --i) {
            arr[i] = arr[j];
            if (arr[j] == 0) arr[--i] = 0;
        }
    }
}

// Code language: C++
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int i = n - 1, j = 0, cnt = 0;
        for ( ; cnt < n; ++j, ++cnt) {
            if (arr[j] == 0) ++cnt;
        }
        if (arr[--j] == 0 && cnt > n) {
            arr[i--] = 0;
            --j;
        }
        for (; i > 0; --j, --i) {
            arr[i] = arr[j];
            if (arr[j] == 0) arr[--i] = 0;
        }
    }
};

时间复杂度: \(O(n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1089 复写零

题目

标签

题解

模拟

双指针