题目链接:传送门
题目描述:
给定一个数组 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--];
}
}
};
这两道题目就讲到这里了,下次再见!