本文主要是介绍【双指针算法】原地处理数组的双指针算法思想，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
移动零
题目中已经明确表示不能重新创建数组来辅助解题，因此只能对数组进行原地操作，即双指针算法思想。
算法思想：
题目要求我们将非0元素放在数组的左边，0元素放在数组的右边，同时保持非0元素的相对位置。
这种对数组元素进行分类的题目一般用双指针比较合适。
注意：这里的双指针其实指的是数组元素的索引。
首先我们将待处理数组分为三部分区间：非0区间：[0,dest] 0区间：[dest+1,cur-1] 待处理区间：[cur,n-1]
cur：用于遍历数组遇到非0元素则停止。dest：用于交换非0元素与0元素。
1、cur = 0, dest = -1
2、cur遇到0元素：++cur
cur遇到非0元素：swap(a[dest+1], a[cur]),然后++dest,++cur
当cur>n-1则结束。
class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1;cur < nums.size();cur++){if(nums[cur])swap(nums[cur], nums[++dest]);}}
};复写零
这道题目要求也是就地进行数组操作，使用双指针是合适的。
算法思想：
先根据“异地”操作然后优化成“就地”操作。下图是通过异地操作获取最后一个“复写”的数。
1、dest = -1,cur = 0,判断a[cur]的值
2、判断dest是否越界 dest <= n-1
3、a[cur] == 0则dest += 2 a[cur] != 0则dest++
4、cur++
但是这里有一种特殊情况：
找到最后一个复写的元素后按照”从后往前“（因为刚开始从前往后的话，会将后面的元素覆盖掉）的顺序对待处理数组进行复写操作。
class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1;int n = arr.size();//先找到最后一个复写的数while( cur < n){if(arr[cur])++dest;elsedest += 2;if(dest >= n-1)break;++cur;}//处理边界情况if(dest == n){arr[n-1] = 0;--cur;dest -= 2;}//最后从后往前复写元素获得所求数组while(cur >= 0){if(arr[cur])arr[dest--] = arr[cur--];else{arr[dest--] = arr[cur];arr[dest--] = arr[cur--];}}}
};这篇关于【双指针算法】原地处理数组的双指针算法思想的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
