专业网站建设代理,广东知名网站建设,南宁seo外包服务商,快速网站开发工具复写零原题地址
方法一#xff1a;双指针法
从前向后复写#xff0c;会造成覆盖。所以#xff0c;应该从后向前复写#xff0c;这样我们可以考虑维护一个栈。遍历数组#xff0c;如果遇到非零元素#xff0c;就入栈一次#xff1b;如果遇到零#xff0c;就入栈两次。…复写零原题地址
方法一双指针法
从前向后复写会造成覆盖。所以应该从后向前复写这样我们可以考虑维护一个栈。遍历数组如果遇到非零元素就入栈一次如果遇到零就入栈两次。当栈中的元素个数超出数组的元素个数时把栈中的元素重新从后向前写入数组即可。
如对于数组 [1 2 0 0 3 0 4]
1 入栈 1 次 [1]
2 入栈 1 次 [1 2]
0 入栈 2 次 [1 2 0 0]
0 入栈 2 次 [1 2 0 0 0 0]
3 入栈 1 次 [1 2 0 0 0 0 3]
此时栈中元素个数和数组元素个数相等重新写入数组即可。
再举一个例子对于数组 [1 2 0 0 3 0 4 5]
1 入栈 1 次 [1]
2 入栈 1 次 [1 2]
0 入栈 2 次 [1 2 0 0]
0 入栈 2 次 [1 2 0 0 0 0]
3 入栈 1 次 [1 2 0 0 0 0 3]
0 入栈 2 次 [1 2 0 0 0 0 3 0 0]
此时栈中元素个数比数组元素个数多一个需要去掉最后一个零把 [1 2 0 0 0 0 3 0] 写入数组。
由于不允许开辟 O(N) 的额外空间我们可以考虑用 top 来维护栈顶即栈中的有效数据个数模拟出入栈过程。假设数组长度为 n 当 topn 时可以继续入栈。
用下标 i 来记录要复写的元素下标 j 来记录复写的目标位置。在前面模拟入栈的过程中可以记录最后一个入栈的元素在数组中的下标即 i 。由于是从后向前复写 j 要初始化为 n-1 。
对于栈中元素个数比数组元素个数多一个即 topn1 的特殊情况最后一个零只需要复写一次其余情况正常复写即可。复写时把 [0,i] 的元素按照是否为零进行分类非零元素复写一次零复写两次。
// 方法一双指针
class Solution
{
public:void duplicateZeros(vectorint arr){int n arr.size();int top 0; // 记录栈顶int i -1;// 模拟把数组元素放入栈中while (top n){if (arr[i]){top;}else{top 2;}}// i 表示要复写的数据// j 表示要复写的位置int j n - 1;// 最后放入 2 个零导致栈中元素比数组多if (top n 1){arr[j--] 0;--i;}while (j 0){// 第一次复写arr[j--] arr[i];// 零还需要复写第二次if (arr[i--] 0){arr[j--] 0;}}}
};
