文章目录
- 一【题目类别】
- 二【题目难度】
- 三【题目编号】
- 四【题目描述】
- 五【题目示例】
- 六【解题思路】
- 七【题目提示】
- 八【时间频度】
- 九【代码实现】
- 十【提交结果】
一【题目类别】
- 双指针
二【题目难度】
- 简单
三【题目编号】
- 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<=1041 <= arr.length <= 10^41<=arr.length<=104
- 0<=arr[i]<=90 <= arr[i] <= 90<=arr[i]<=9
八【时间频度】
- 时间复杂度:O(n)O(n)O(n),其中nnn为传入的数组的长度
- 空间复杂度:O(1)O(1)O(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--;}}
}
- 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--;}
}
- 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
- 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--;}}
};
十【提交结果】
-
Java语言版
-
C语言版
-
Python语言版
-
C++语言版