LeetCode 题解工作台
复写零
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。 示例 1： 输入： arr = [1,0,2,3,0,4,5,0] 输出： [1,0,0,2…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 双·指针·invariant
答案摘要
开辟一个等长数组，将 `arr` 复刻一份，再进行简单模拟即可。 - 时间复杂度：。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个长度固定的整数数组 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
解题思路
方法一：模拟
开辟一个等长数组，将 arr 复刻一份，再进行简单模拟即可。
- 时间复杂度：。
- 空间复杂度：。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) because each element is scanned at most twice, and space complexity is O(1) since all operations modify the array in place without extra arrays or buffers. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Are you tracking how duplicating zeros affects element positions?
- question_mark
Can you solve this in-place without extra storage?
- question_mark
How do you handle zeros at the end that would overflow the array?
常见陷阱
外企场景- error
Overwriting elements before they are duplicated when scanning left to right.
- error
Failing to handle zeros at the last valid index correctly, causing array overflow.
- error
Using extra arrays which violates the in-place modification requirement.
进阶变体
外企场景- arrow_right_alt
Duplicate a specific value other than zero while shifting elements in place.
- arrow_right_alt
Duplicate zeros but allow dynamic array expansion instead of fixed length.
- arrow_right_alt
Count the total duplicates of zeros without modifying the original array in place.