复写零
题目链接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]
题目解释
解释一下题意.什么是复写0,说人话就是我们的遍历整个数组,如果我们遇到一个元素,判断这个元素.
- 如果是0,那么新增两个0
- 如果不是0, 直接添加
我们遍历整个数组之后,然后裁出来和原本数组长度相等的子数组就是我们的结果.
算法原理
先说一下这个题目,本来是是非常简单的,我们可以借助一个辅助数组,然后遍历我们原来的数组,下面是我们遇到的两个情况
- 遇到的元素是 0: 新数组里面尾插两个0
- 遇到的元素非 0: 新数组里面将这个元素尾插
int n = nums.size();
vector<int> new_num(n);
int index = 0;
for(int i = 0; i < n; ++i)
{
if(nums[i] == 0)
{
new_num[index++] = 0;
new_num[index++] = 0;
}
else
{
new_num[index++] = nums[i];
}
if(index == n) break;
}
// 将new覆盖回去就可以了
这里我们又发现一个规律,我们使用了一个辅助数组,那么是不是可以说使用双指针?可以的,但是这里存在一个情况,我们的辅助数组的p2可能会比我们原数组跑的快,那么这就是造成一个问题,我们后面的元素会被覆盖,
这里我们也是可以使用双指针的,只不过我们需要从右向左走.对于原来数组的一个元素,他的目标位置有两个情况
- 源位置和一个目标位置 这个元素非0
- 原位置和两个目标位置 这个元素是0
下面我们遍历一边数组,根据题意的规则我们可以找到我们的目标位置达到n-1就可以了.这个解决了我们元素被覆盖的问题,但是存在下面一个问题.考虑一下下面的情况
我们dst为何可以到达下标n,这是因为我们的dst有可能跳2个位置,那么为何出现这种情况呢?一定是n-2位置的元素是0,这样他的目标位置就会覆盖后面的两个,所以我们需要解决一下.
下面是解决的办法
if (dest == n)
{
arr[n - 1] = 0;
src--;
dest -= 2;
}
代码编写
class Solution
{
public:
void duplicateZeros(vector<int> &arr)
{
int src = 0;
int dest = -1;
int n = arr.size();
while (src < n)
{
if (arr[src] != 0)
{
dest++;
}
else
{
dest += 2;
}
if (dest >= n - 1)
break;
src++;
}
if (dest == n)
{
arr[n - 1] = 0;
src--;
dest -= 2;
}
// 找到我们的数据并且可以将我们的src的元素赋值给我们的dest
while (src >= 0)
{
if (arr[src] != 0)
{
arr[dest] = arr[src];
dest--;
}
else
{
arr[dest] = arr[src];
arr[dest - 1] = arr[src];
dest -= 2;
}
src--;
}
}
};