企业官网建设流程全解析

【LeetCode 刷题笔记】1089. 复写零（Duplicate Zeros）

📌 题目链接

1089. 复写零

📝 题目大意

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

要求：

• 不能在超过原数组长度的位置写入元素。
• 必须原地（In-place）修改数组，不需要返回值。

💡 解法一：模拟法（vector::insert暴力覆盖）

1. 思路分析

遍历数组，当遇到0时，调用arr.insert()在当前位置插入一个0，同时调用arr.pop_back()弹出末尾元素以维持数组长度不改变。插入后需要将下标i额外自增一次（即i++），跳过刚刚复写的0，避免陷入死循环。

2. 代码实现 (C++)

classSolution{public:voidduplicateZeros(vector<int>&arr){for(inti=0;i<arr.size();i++){if(arr[i]==0){arr.insert(arr.begin()+i,0);// 在位置 i 插入 0arr.pop_back();// 保持数组长度固定i++;// 跳过复写的 0}}}};

3. 复杂度分析

• 时间复杂度：O ( N 2 ) O(N^2)O(N2)。vector::insert需要挪动后续所有元素，单次操作O ( N ) O(N)O(N)，最坏情况下遍历加插入需要O ( N 2 ) O(N^2)O(N2)。
• 空间复杂度：O ( 1 ) O(1)O(1)。原地修改，没有使用额外空间。

🚀 解法二：双指针（快慢指针 + 从后往前填充）—【最优解】

1. 思路分析

由于正序覆盖会导致未处理的元素被提前遮盖，最佳思路是倒序填充。

具体步骤如下：

1. 寻找边界（第一趟遍历）：假设数组能够拓展，用指针i遍历数组，同时用top记录复写后的虚拟长度。当top >= n时停止，此时i指向的就是最终能保留在数组里的最后一个有效元素。
2. 处理边界特例：如果最后一个元素是0且top == n + 1，说明这个0只能被复写一次（空间不足以写入第二个0）。此时手动将数组末尾填入0，并将指针相应前移。
3. 倒序填充（第二趟遍历）：用指针j = n - 1指向原数组末尾，从i开始向前遍历：
   • 若arr[i] == 0，则在j和j - 1位置均填入0（j向前移动 2 位）。
   • 若arr[i] != 0，则将arr[i]复制给arr[j]（j向前移动 1 位）。

2. 代码实现 (C++)

classSolution{public:voidduplicateZeros(vector<int>&arr){intn=arr.size();inttop=0;inti=-1;// 1. 确定最后一个需要复写的元素位置 iwhile(top<n){i++;if(arr[i]==0){top+=2;}else{top+=1;}}// 2. 特殊处理：边界处的 0 只能复写一次的情况intj=n-1;if(top==n+1){arr[j--]=0;i--;}// 3. 从后往前进行复写while(j>=0){if(arr[i]==0){arr[j--]=0;arr[j--]=0;}else{arr[j--]=arr[i];}i--;}}};

3. 复杂度分析

• 时间复杂度：O ( N ) O(N)O(N)。两次单重循环遍历数组。
• 空间复杂度：O ( 1 ) O(1)O(1)。仅使用常数级别额外空间。