Question

1089. 复写零

English Version

题目描述

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

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

 

示例 1：

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

示例 2：

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

 

提示：

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

解法

方法一：模拟

开辟一个等长数组，将 arr 复刻一份，再进行简单模拟即可。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

class Solution:
  def duplicateZeros(self, arr: List[int]) -> None:
    """
    Do not return anything, modify arr in-place instead.
    """
    n = len(arr)
    i, k = -1, 0
    while k < n:
      i += 1
      k += 1 if arr[i] else 2
    j = n - 1
    if k == n + 1:
      arr[j] = 0
      i, j = i - 1, j - 1
    while ~j:
      if arr[i] == 0:
        arr[j] = arr[j - 1] = arr[i]
        j -= 1
      else:
        arr[j] = arr[i]
      i, j = i - 1, j - 1

class Solution {
  public void duplicateZeros(int[] arr) {
    int n = arr.length;
    int i = -1, k = 0;
    while (k < n) {
      ++i;
      k += arr[i] > 0 ? 1 : 2;
    }
    int j = n - 1;
    if (k == n + 1) {
      arr[j--] = 0;
      --i;
    }
    while (j >= 0) {
      arr[j] = arr[i];
      if (arr[i] == 0) {
        arr[--j] = arr[i];
      }
      --i;
      --j;
    }
  }
}

class Solution {
public:
  void duplicateZeros(vector<int>& arr) {
    int n = arr.size();
    int i = -1, k = 0;
    while (k < n) {
      ++i;
      k += arr[i] ? 1 : 2;
    }
    int j = n - 1;
    if (k == n + 1) {
      arr[j--] = 0;
      --i;
    }
    while (~j) {
      arr[j] = arr[i];
      if (arr[i] == 0) arr[--j] = arr[i];
      --i;
      --j;
    }
  }
};

func duplicateZeros(arr []int) {
  n := len(arr)
  i, k := -1, 0
  for k < n {
    i, k = i+1, k+1
    if arr[i] == 0 {
      k++
    }
  }
  j := n - 1
  if k == n+1 {
    arr[j] = 0
    i, j = i-1, j-1
  }
  for j >= 0 {
    arr[j] = arr[i]
    if arr[i] == 0 {
      j--
      arr[j] = arr[i]
    }
    i, j = i-1, j-1
  }
}

impl Solution {
  pub fn duplicate_zeros(arr: &mut Vec<i32>) {
    let n = arr.len();
    let mut i = 0;
    let mut j = 0;
    while j < n {
      if arr[i] == 0 {
        j += 1;
      }
      j += 1;
      i += 1;
    }
    while i > 0 {
      if arr[i - 1] == 0 {
        if j <= n {
          arr[j - 1] = arr[i - 1];
        }
        j -= 1;
      }
      arr[j - 1] = arr[i - 1];
      i -= 1;
      j -= 1;
    }
  }
}

void duplicateZeros(int* arr, int arrSize) {
  int i = 0;
  int j = 0;
  while (j < arrSize) {
    if (arr[i] == 0) {
      j++;
    }
    i++;
    j++;
  }
  i--;
  j--;
  while (i >= 0) {
    if (arr[i] == 0) {
      if (j < arrSize) {
        arr[j] = arr[i];
      }
      j--;
    }
    arr[j] = arr[i];
    i--;
    j--;
  }
}

方法二：双指针

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。