简单

问题描述

给你一个长度固定的整数数组 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$ 之后接下来需要输出的数字，当遇到第一个 $0$ 时，入队一个 $0$（意思是当前 $0$ 的下一个数字是 $0$），然后继续遍历，当队列不为空时，将当前数字入队，如果当前数字是 $0$，则入队两次，然后队首元素出队，占领当前位置。

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function (arr) {
  const queue = []
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    if (queue.length) {
      if (num === 0) {
        queue.push(0)
      }
      queue.push(num)
      arr[i] = queue.shift()
    } else if (num === 0) {
      queue.push(0)
    }
  }
}

• 时间复杂度：$O(n)$，需要遍历数组一次。
• 空间复杂度：$O(n)$，需要一个队列来存放后续的数。

栈

创建一个栈，遍历数组，当遇到 $0$ 时，将 $0$ 入栈两次，非 $0$ 时，则入栈一次，当栈的长度跟原来数组长度一致时，停止遍历，这样就获得了一个复写 $0$ 后效果的栈，然后倒序遍历数组，将栈内容改写到数组中。

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function (arr) {
  const n = arr.length
  const stack = []
  for (let i = 0; i < n; i++) {
    if (arr[i] === 0) {
      stack.push(arr[i])
      if (stack.length === n) break
    }
    stack.push(arr[i])
    if (stack.length === n) break
  }
  for (let i = n - 1; i > -1; i--) {
    arr[i] = stack.pop()
  }
}

• 时间复杂度：$O(n)$，需要遍历数组两次。
• 空间复杂度：$O(n)$，需要开辟一个跟原数组相同大小的栈空间。

双指针

使用 $i$ 和 $j$ 两个指针，可以想像 $i$ 是指向原数组的头部位置，$j$ 指向目标数组的头部位置。然后开始遍历数组遇到过非 $0$ 的数时，$i$ 和 $j$ 同时向后移动一个位置，如果遇到 $0$，则 $i$ 移动一个位置，$j$ 是指向目标数组，需要复写零，所以移动两个位置。当 $j$ 大于等于数组长度 $n$ 时停止遍历。

当 $j$ 走到的位置已超出数组长度时，$i$ 停在了需要被截断的位置的下一位，所以 $i$ 和 $j$ 都左移一位，让 $i$ 指向截断的最后一位的位置。要注意的是，如果最后一位是 $0$ 的情况下，$j$ 此时为 $n$，所以为了确保 $j$ 是合法的，需要加上 $j < n$ 的判断，当 $j < n$ 时，此时 $j$ 的位置应该是当前 $i$ 所指的位置值，所以有 $arr[j] = arr[i]$，然后 $j$ 左移一位，如果当前 $arr[i] = 0$，那么需要复写一个 $0$，把当前 $arr[j]$ 赋值为 $0$ 后，$j$ 再左移一位。然后 $i$ 左移一位，如此往复，直到 $i$ 退到数组之外，即 $i < 0$。

/**
 * @param {number[]} arr
 * @return {void} Do not return anything, modify arr in-place instead.
 */
var duplicateZeros = function (arr) {
  const n = arr.length
  let i = 0
  let j = 0
  while (j < n) {
    if (arr[i] == 0) j++
    i++
    j++
  }
  i--
  j--
  while (i >= 0) {
    if (j < n) arr[j] = arr[i]
    j--
    if (arr[i] == 0) {
      arr[j] = 0
      j--
    }
    i--
  }
}

• 时间复杂度：$O(n)$，需要遍历数组两次。
• 空间复杂度：$O(1)$