题目：复写零

  • 给你一个长度固定的整数数组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

来源：力扣（LeetCode）第1089题

链接：https://leetcode-cn.com/problems/duplicate-zeros

分析：

这道题的难点在于要在原数组上操作，不可以申请新的数组。因此，快慢双指针就派上用场了。

思路：

  • 声明两个指针i,j
  • 一个指针正常遍历i，另一个j遇到0就往前再+1
  • 遍历完之后i之后的数都是被移出去的，j指针在最后一位
  • 依次将i指针的元素赋在j的位置，遇到0，j不仅要将i的值赋上，还要往前一位再赋上0。

代码：

  • 双指针法：

    class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
    i = j = 0
    n = len(arr)
    while j < n:
        if arr[i] == 0:
            j += 1
        i += 1
        j += 1
    i -= 1
    j -= 1
    while i >= 0:
        if j < n:
            arr[j] = arr[i]
        if arr[i] == 0:
            j -= 1
            arr[j] = 0
        j -= 1
        i -= 1

  • 非原地解法：

    class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
    i = 0
    while i < len(arr):
        if arr[i] == 0:
            arr.insert(i, 0)
            arr.pop()
            i += 1
        i += 1

复杂度分析：

  • 时间复杂度：O(n) n为数组的长度
  • 空间复杂度：O(1)