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

【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(vectorintarr){for(inti0;iarr.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. 思路分析由于正序覆盖会导致未处理的元素被提前遮盖最佳思路是倒序填充。具体步骤如下寻找边界第一趟遍历假设数组能够拓展用指针i遍历数组同时用top记录复写后的虚拟长度。当top n时停止此时i指向的就是最终能保留在数组里的最后一个有效元素。处理边界特例如果最后一个元素是0且top n 1说明这个0只能被复写一次空间不足以写入第二个0。此时手动将数组末尾填入0并将指针相应前移。倒序填充第二趟遍历用指针j n - 1指向原数组末尾从i开始向前遍历若arr[i] 0则在j和j - 1位置均填入0j向前移动 2 位。若arr[i] ! 0则将arr[i]复制给arr[j]j向前移动 1 位。2. 代码实现 (C)classSolution{public:voidduplicateZeros(vectorintarr){intnarr.size();inttop0;inti-1;// 1. 确定最后一个需要复写的元素位置 iwhile(topn){i;if(arr[i]0){top2;}else{top1;}}// 2. 特殊处理边界处的 0 只能复写一次的情况intjn-1;if(topn1){arr[j--]0;i--;}// 3. 从后往前进行复写while(j0){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)。仅使用常数级别额外空间。