【双指针】专题：LeetCode 283题解——移动零

一、题目链接

移动零

二、题目

三、题目解析

“保持非零元素的相对顺序”，比如，示例1中非零元素1在前、3在中间、12在最后，那么移动完数据后还是要保持1在前、3在中间、12在最后，也就是一直保持[1, 3, 12]的顺序。

四、算法原理

移动零这题是可以划分到数组划分/数组分块这一类题里的。

数组划分/数组分块的特点：给一个数组，在制定的规则/标准下将数组划分若干个区间。

本题中制定的规则/标准就是将非0元素移动到数组的前面，0元素移动到数组的后面。因此在该规则下可以把数组划分成两个区间。

数组划分/数组分块这一类题里涉及到的算法就是双指针算法，但是数组中不是真的用int*这样的指针，数组中是利用数组下标来充当指针。

---

已处理的区间的目的是达成题目中的要求：已处理区间中左边区间是非0元素，右边区间是0元素。而dest就是非0元素与0元素的分割线。

两个指针的作用以及三个区间

两个指针的作用：
cur：从左往右遍历数组。
dest：已处理的区间内，非零元素的最后一个位置。

三个区间：

都是左闭右闭区间

---

两个指针的作用以及三个区间要在解题过程中牢记

cur要遍历数组，所以一开始在下标0处。dest一开始在下标-1处，原因是还没有处理数据。（牢记两个指针的作用以及三个区间，这时是满足的。）这时cur指向元素0。

当cur遇到元素0，不做任何处理，直接++cur。（满足两个指针的作用以及三个区间，元素0区间[dest + 1，cur - 1]此时就一个0；待处理区间[cur，n - 1]）这时cur指向非0元素。

当cur指向非0元素，非0元素肯定要放到第一个区间的，加一个非0元素就要dest++，然后交换cur、dest指向的元素（注意：不是向前覆盖，这样元素0就不见了）。此时cur所指元素是已经处理过了，所以cur++（满足两个指针的作用以及三个区间）。上述过程转换成代码：swap(dest + 1，cur); dest++，cur++;

---

重复上述过程，cur为下标n（数组的元素）时就跳出循环。最后这块数组是被划分成两个区间，即非0元素区间以及0元素区间。

---

总结

cur从前往后遍历的过程中：
1、遇到 0 元素：cur++
2、遇到 非0 元素：swap(dest + 1，cur); cur++，dest++;

五、与快速排序的联系

其实快速排序的核心就是数组分块，若是像本题一样用双指针算法，根据基准元素tmp将数组划分成2个区间，那么分析过程以及代码都是与本题一样的。

#include <iostream>
using namespace std;
int _QuickSort(int arr[], int left, int right)
{int keyi = left;int dest = keyi;for (int cur = dest + 1; cur <= right; ++cur)if (arr[cur] <= arr[keyi] && ++dest != cur )swap(arr[cur], arr[dest]);swap(arr[keyi], arr[dest]);return dest;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}// 找基准值的下标int keyi = _QuickSort(arr, left, right);// [left, keyi - 1]  [keyi + 1, right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}
int main()
{int arr[] = { 6, 1, 2, 7, 9, 3 };size_t n = sizeof(arr) / sizeof(arr[0]);QuickSort(arr, 0, n - 1);for (size_t i = 0; i < n; ++i){cout << arr[i] << " ";}cout << endl;return 0;
}

快速排序这里用双指针算法，只是把数组分成两块，一旦遇到都是相同的数据时，时间复杂度会逼近O(n^2)。

后面“颜色划分”一题，会把数组划分成三块，用这一算法写快速排序才是最优的。

六、编写代码

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

简化代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int dest = -1, cur = 0; cur < nums.size(); cur++)// nums[cur]为0还是非0都会++if (nums[cur])// 处理非0元素swap(nums[++dest], nums[cur]);}
};

七、时间复杂度、空间复杂度

一层for循环，cur、dest指针只会从前向后移动，并且这里只判断cur，也就是cur扫描数组一遍就能将数组划分，因此时间复杂度是最优的O(n)。

只用了两个变量cur、dest，因此空间复杂度是O(1)。