建设网站的好处,网站建设在线菜鸟教程,建一个自己的网站有什么用,营销型官方网站常⻅的双指针有两种形式#xff1a;
1 对撞指针#xff08;左右指针#xff09;#xff1a;
a 对撞指针从两端向中间移动。⼀个指针从最左端开始#xff0c;另⼀个从最右端开始#xff0c;然后逐渐往中间逼 近
b 终止条件一般是两指针相遇or错过#xff08;也可能在循…常⻅的双指针有两种形式
1 对撞指针左右指针
a 对撞指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼 近
b 终止条件一般是两指针相遇or错过也可能在循环过程中找到结果直接跳出循环即 left right 两个指针指向同⼀个位置 left right 两个指针错开
2 快慢指针 使⽤两个移动速度不同的指针在数组或链表等结构上移动 特别是处理环形链表或数组时有很大用处也就是说当问题出现循环往复的情况时可考虑使用快慢指针的思想 题目
给定一个数组 编写一个函数将所有 移动到数组的末尾同时保持非零元素的相对顺序。nums0
请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 1:
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums [0]
输出: [0]
代码实现
class Solution
{
public:void moveZeroes(vectorint nums){int cur 0;//遍历数组int pre -1;//指向非0元素区域中最后一个非0元素while(curnums.size()){if(nums[cur])//找到非0元素{swap(nums[pre],nums[cur]);//将非0元素与0元素交换pre指向的一定是0元素}cur;}}
};
思路详解
题目要求实现的功能可以说是数组划分数组分块让非0元素排在前半部分0元素排在后半部分且要求元素间的相对顺序保持不变。
方法
前后指针法
此处的指针是用数组的下标来充当的并不是真正意义上的指针
1 cur指针去从左向右遍历数组只需要一直向前走就行指向的是待处理的元素
2 pre指针记录已处理区间内的非0元素区域最后一个非0元素的下标
cur初始化为0因为要从0下标开始遍历
pre初始化为-1因为pre指向的是已处理区间中的非0元素区的最后一个非0元素下标刚开始还没有确定任何一个元素是否是非0元素
思想
cur负责遍历数组指向待处理的元素
找到的是非0元素则将它交换到前面
找到的是0元素则视而不见直接走向下一个待处理元素
pre指向的始终是已处理区间中的非0元素区的最后一个非0元素的下标cur因为遇到0而不断与pre拉开距离
那么[pre1,cur-1]的区间是已处理区间中的0元素区 在处理过程中数据分三区
[0,pre]全都是非0元素
[pre1,cur-1]全是0元素
[cur,n-1]n是数组元素个数是待处理的元素 简单来说就是cur在遍历过程中若是遇到非0元素则将它与0元素交换让非0元素换到前面0元素换到后面[pre1,cur-1]的区域内全是0元素遇到0元素则不管直接找下一个待处理元素 完结撒花~
题外话解决此题目的前后指针法其实和快排中实现数组划分的方法之一类似也可以成之为前后指针法但是实现略有差异且在实现后快排中数组元素的相对顺序可能会发生改变
详情在我的另一篇快排模拟实现的博客中
http://t.csdn.cn/2Km96
