搜索引擎及门户网站介绍总结,济南市建设执业资格注册中心网站,中国做外贸的网站有哪些,找设计师的网站复写零 题目链接1089. 复写零 给你一个长度固定的整数数组 arr #xff0c;请你将该数组中出现的每个零都复写一遍#xff0c;并将其余的元素向右平移。 注意#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改#xff0c;不要从函数返回…复写零 题目链接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();
vectorint 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(vectorint 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的元素赋值给我们的destwhile (src 0){if (arr[src] ! 0){arr[dest] arr[src];dest--;}else{arr[dest] arr[src];arr[dest - 1] arr[src];dest - 2;}src--;}}
};
