难度: Easy
给你一个长度固定的整数数组 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 <= 1040 <= arr[i] <= 9运行时间: 22 ms
内存: 16.3 MB
from typing import List
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
zeros_count = 0
length = len(arr)
# Count the number of zeros in the array
for num in arr:
if num == 0:
zeros_count += 1
# Calculate the new length after duplicating zeros
new_length = length + zeros_count
# Iterate the array from the end, shifting elements to the right
i = length - 1
while i >= 0 and i < new_length:
if i < length and arr[i] == 0:
# Duplicate zero by inserting it at the current position
if i + zeros_count < new_length:
arr.insert(i + zeros_count, 0)
zeros_count -= 1
# Shift the element to the right
if i + zeros_count + 1 < new_length:
arr[i + zeros_count + 1] = arr[i]
i -= 1
from typing import List
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
zeros_count = 0
length = len(arr)
# Count the number of zeros in the array
for num in arr:
if num == 0:
zeros_count += 1
# Calculate the new length after duplicating zeros
new_length = length + zeros_count
# Use two pointers to modify the array in-place
i = length - 1 # Pointer to iterate over the original array
j = new_length - 1 # Pointer to place the modified elements
while i >= 0:
if arr[i] == 0:
# Duplicate zero only if there's enough space
if j < length:
arr[j] = 0
j -= 1
# Always duplicate zero
if j < length:
arr[j] = 0
else:
# Shift the non-zero element to its new position
if j < length:
arr[j] = arr[i]
i -= 1
j -= 1
题解采用了一种双指针技术来就地修改数组。首先，数组中的零的数量被计算出来，并利用这个信息计算出如果全部复写零后的数组长度。接着，从数组的末尾开始，使用两个指针i和j进行操作：i指向原始数组的末尾，j指向复写零后的虚拟数组末尾。迭代过程中，如果遇到零，则需要在j指向的位置上复写零，如果有空间则复写两次。如果不是零，则将元素复制到j指向的位置。这个过程一直持续到i遍历完数组的开头。
时间复杂度: O(n)
空间复杂度: O(1)
from typing import List
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
# Step 1: Count the number of zeros in the original array
zeros_count = 0
length = len(arr)
for num in arr:
if num == 0:
zeros_count += 1
# Step 2: Initialize pointers for the original and modified array positions
i = length - 1 # Pointer to the original array's end
new_length = length + zeros_count
j = new_length - 1 # Pointer to the virtual new array's end
# Step 3: Iterate from the end, placing elements and duplicating zeros
while i >= 0:
if arr[i] == 0:
# Place zero in the new position if within bounds
if j < length:
arr[j] = 0
j -= 1
# Duplicate the zero again if within bounds
if j < length:
arr[j] = 0
else:
# Place the current element in its new position if within bounds
if j < length:
arr[j] = arr[i]
i -= 1
j -= 1
题解中，尽管计算了新数组的长度（原数组长度加上零的数量），实际操作并不会创建一个真正的新数组，而是利用原数组进行模拟。这种方法通过设置一个虚拟的末尾指针j来模拟新数组，同时确保所有实际的写入操作都不会超出原数组的边界（通过`if j < length`判断）。这种方式确保了不会因数组长度限制而覆盖或访问数组外的内存。
虚拟数组的长度计算是为了确定在包含复写零后的数组中每个元素的正确位置。如果直接在原数组上进行修改，由于零的复写会导致数组中的元素向后移动，可能会覆盖还未处理的元素，从而导致数据丢失或错误。通过计算虚拟数组长度，并从数组的末尾开始复制和复写零，可以避免这种覆盖，确保每个元素都被正确放置。
虚拟数组并不是一个实际存在的数组，而是一个在逻辑上通过计算得出的假设数组，它包含了原数组中的所有元素以及复写的零。虚拟数组的长度由原数组的长度加上原数组中零的数量决定。在实际操作中，我们通过移动指针j来模拟这个虚拟数组的索引，从而确定每个元素（包括复写的零）在原数组中应该放置的位置。
这个判断用于确保不会在原数组的长度外进行写操作，即不会覆盖数组外的内存。由于j的值可能会超出原数组的实际长度（在虚拟数组中），这个判断确保只有当j仍在原数组的有效范围内时才进行元素的复写或复制。通过调整i和j的初始位置可以减少边界检查的次数，但完全避免这种检查并不可行，因为我们需要确保每次写入都在安全的数组范围内。