承德网站开发成人培训机构

一、双指针

1.1移动零

链接：283. 移动零 - 力扣（LeetCode） 

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0] 

解法：

通过两个指针（并非是真的指针，只是数组的下标），dest和cur将长度为n的数组划分为三个部分；

[0,dest]：cur已经遍历过的地方，处理过不为0的部分；

[dest+1,cur-1]：cur已经遍历过的地方，处理过为0的部分；

[cur,n-1]：cur未遍历的地方；

---

第一种情况： cur指向数组元素为0

[0,dest]部分是处理过并且元素不为0的部分，cur指向0，所以处理后[0,dest]不变；

[dest+1,cur-1]部分是处理过为0的部分，所以处理后[dest+1,cur-1]长度加一；

[cur,n-1]部分长度减一；

 第二种情况： cur指向数组元素不为0

[0,dest]部分是处理过并且元素不为0的部分，cur指向1，所以处理后[0,dest]长度加一，dest往后移一位，用来存放1；

[dest+1,cur-1]部分是处理过为0的部分，所以处理后[dest+1,cur-1]长度不变；

[cur,n-1]部分长度减一；

 dest往后移一位，dest指向为0的部分，只需要将此时的dest指向和cur指向元素交换即可，之后cur++；

---

初始状态，dest=-1，cur=0；

1.nums[cur]为0，cur++；

2.nums[cur] 不为0，dest++后，在交换nums[dest]和nums[cur];

c++解法： 

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int dest=-1,cur=0; cur<nums.size(); cur++){if(nums[cur])swap(nums[cur], nums[++dest]);}}
};

c语言解法： 

void moveZeroes(int* nums, int numsSize) 
{for(int dest=-1,cur=0; cur<numsSize; cur++){if(nums[cur]){       int temp = 0;temp = nums[++dest];nums[dest] = nums[cur];nums[cur] = temp;}}
}

---

---