双指针算法解决 移动零 和 复写零问题
一、移动零
题目链接:传送门
题目描述:
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
注意要求: 必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:
输入: nums = [0] 输出: [0]
🍟解题思路:
本篇文章使用双指针算法解决,思路如下: 首先,虽然叫"双指针",但不一定非要是两个指针,这只是一种形象的说法,比如此题是数组,可以用两个整形变量作为下标.
- 创建一个"指针"
cur,使其指向数组中第一个出现的0的位置.(如果数组中没有0,则直接返回). - 创建第二个"指针"
dest,从cur的下一个位置开始. - ①如果
dest指向的值是0,则继续dest继续往后遍历. ②如果dest指向的值是非0,则与cur进行交换. - 当
dest遍历结束,则完成要求.
我们这样操作可以将0都夹在cur和dest两个指针之间,最后dest指向最后,则0就全到数组最后面了.
图解:
🍔代码实现:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int sz=nums.size();
int cur=0;
//cur指针指向数组中第一个0
while(nums[cur]!=0 && cur!=sz-1){
++cur;
}
if(cur==sz-1)return ; //如果没有0,则直接返回
//dest指针从cur指针的下一个开始
int dest=cur+1;
while(dest!=sz){
if(nums[dest]!=0){ //如果这个数非0,则与cur交换
swap(nums[cur],nums[dest]);
cur++;
}
++dest;
}
}
};二、复写零
题目链接:传送门
题目描述:
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意要求: 请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
🍟解题思路:
如果我们直接从左往右开始复写,当遇到0,需要复写两次0的时候,会将后面的数字给覆盖掉.
我们采取从后往前覆盖的方法.
- 创建一个"指针"
cur和一个"指针"dest. cur指向最后一个需要复写的元素,dest指向复写后最后元素的位置.
那么如何找到这两个位置呢?
很简单,模拟一下复写过程即可.
cur往后遍历时,遇到非0,dest往后走一步. 遇到0,dest往后走两步. 当dest走到最后一个元素的时候,结束,此时cur和dest都到达了指定位置.
处理特殊情况:
出界原因:
由于dest可能一次跳2步,很可能从倒数第二个位置+2直接出界,此时需要特殊处理.
导致出界,说明当dest指向倒数第二个位置的时候,cur指向0,则表明最后一个位置应该设置为0.
处理方式:
①将最后一个元素复写为0 .
②dest-向左两步,指向倒数第二个位置.
③cur向前一步.
- 最后:从右往左遍历,完成正常的复写.
图解:
🍔代码实现
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1;
int sz = arr.size();
//让cur指向最后一个复写的位置,dest指向完成复写后最后一个元素的位置
while (dest < sz) {
if (arr[cur] == 0) {
dest+=2;
}else ++dest;
if (dest >= sz - 1)break;
++cur;
}
//处理特殊情况
if (dest == sz) {
arr[sz-1] = 0;
dest-=2;
--cur;
}
//从后往前复写
while (cur >= 0) {
if (arr[cur] == 0) {
arr[dest--] = arr[cur];
}
arr[dest--] = arr[cur--];
}
}
};这两道题目就讲到这里了,下次再见!
腾讯云开发者
