一【题目类别】

• 双指针

二【题目难度】

• 简单

三【题目编号】

• 1089.复写零

四【题目描述】

• 给你一个长度固定的整数数组 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]

六【解题思路】

• 这道题如果不使用任何API，那么难度就是困难级别，用双指针来做确实不太好想
• 我们可以定义两个指针：
  • 指针top：虚拟的栈指针，遇到符合题目要求的数字虚拟进栈，此虚拟的栈指针是虚栈顶，也就是说top指向的前一个位置才是真正的元素
  • 指针i：指向最后一个符合题目要求的数字的位置
• 扫描数组之后，符合题目要求的数字已经被我们保留好了，而且也给零预留了位置，但是有个细节需要注意，如果最后一个是零，我们需要先把零放入结果数组中，并且指针向前移动，也就是说，我们要单独处理这个零
• 最后就是从后向前扫描数组，如果当前数字是零，就按照预留的位置填两个零；如果当前数字不是零，就正常填写
• 本题不需要返回值
• 特别提醒：本题较复杂，强烈建议在用笔纸模拟一下

七【题目提示】

• $1<=arr.length<=10^4$
• $0<=arr[i]<=9$

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为传入的数组的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {public void duplicateZeros(int[] arr) {int len = arr.length;int top = 0;int i = -1;while(top < len){i++;if(arr[i] != 0){top++;}else{top+=2;}}int j = len - 1;if(top == len + 1){arr[j] = 0;i--;j--;}while(j >= 0){arr[j] = arr[i];j--;if(arr[i] == 0){arr[j] = arr[i];j--;}i--;}}
}

2. C语言版

void duplicateZeros(int* arr, int arrSize)
{int i = -1;int top = 0;while(top < arrSize){i++;if(arr[i] != 0){top++;}else{top+=2;}}int j = arrSize - 1;if(top == arrSize + 1){arr[j] = 0;i--;j--;}while(j >= 0){arr[j] = arr[i];j--;if(arr[i] == 0){arr[j] = arr[i];j--;}i--;}
}

3. Python语言版

class Solution:def duplicateZeros(self, arr: List[int]) -> None:size = len(arr)i = -1top = 0while top < size:i+=1if arr[i] == 0:top+=2else:top+=1j = size - 1if top == size + 1:arr[j] = 0j-=1i-=1while j >= 0:arr[j] = arr[i]j-=1if arr[i] == 0:arr[j] = arr[i]j-=1i-=1

4. C++语言版

class Solution {
public:void duplicateZeros(vector<int>& arr) {int len = arr.size();int i = -1;int top = 0;while(top < len){i++;if(arr[i] == 0){top+=2;}else{top++;}}int j = len - 1;if(top == len + 1){arr[j]=0;j--;i--;}while(j >= 0){arr[j] = arr[i];j--;if(arr[i] == 0){arr[j] = arr[i];j--;}i--;}}
};

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版
   

4. C++语言版