算法从0到100之【专题一】-双指针第一练（数组划分、数组分块）

文章目录 【题目一】移动零题目要求算法原理（思路讲解 + 画图模拟演示）代码实现 【题目二】复写零题目要求算法原理（思路讲解 + 画图模拟演示）代码实现

【题目一】移动零 题目要求

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

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

示例 2: 输入: nums = [0] 输出: [0]

提示: 1 <= nums.length <= 104 -2^31 <= nums[i] <= 2^31 - 1

进阶：你能尽量减少完成的操作次数吗？ 原题链接

算法原理（思路讲解 + 画图模拟演示）

数组划分/数组分块这类题的特点： 给我们一个数组，给我们制定一个标准/规则，让我们在这个规则下把数组划分成若干个区间。

而移动零这道题就相当于给我们一个数组，而标准是非零元素移到左边，而 0 元素移到右边，在这个标准下把数组分成两个区间（非 0 元素在左区间， 0 元素在右区间）。 而解决这类题的一个很经典的算法就是双指针算法。 这里的 "双指针” 并非真正的指针，在数组中，我们可以利用数组下标来充当指针的作用。因为数组下标就能索引到数组中的元素，所以没有必要定义指针。

思路：定义两个下标变量（“指针”） dest（destination） ，cur（current） ；两个指针往后走的时候会把数组分成三个区间，而 cur 从左往右扫描数组（遍历数组），dest 则标记已处理的区间内（已处理就是达到这个区间左边都是非零元素，右边都是零元素的目的）的非零元素的最后一个位置；那两个指针就把数组划分为了三个区间：[0,dest]，[dest + 1,cur - 1]，[cur,n-1] ，n是数组元素个数，[0,dest]区间都是非零元素，[dest + 1,cur - 1]都是 0 元素，[cur,n-1]是待处理的区间，如果我们能保证 dest 和 cur 向右移动的过程中，三个区间都能保持这三个性质，那当 cur 移动到 n 位置的时候（数组遍历完成），那我们的区间就划分完成了，这时候题目也完成了。 如下图：

那如何做到保持三个区间的性质不变呢？ 很简单，当 cur 从前往后遍历的过程中会遇到两种情况（ 0元素和非零元素）： 1、遇到 0 元素：cur++ 2、遇到非 0 元素：dest++，交换 dest 和 cur 指向的元素，cur++ 即可。 如下图：

题外话：上面双指针的思想其实就是快速排序里面最核心的一步（数据划分，定义一个 tmp，让 tmp 左边的元素小于 tmp，tmp 右边的元素大于 tmp），忘记的同学可以去复习一下快速排序。但是当数据很大且很多相同的时候，这种方法的快排的时间复杂度是逼近 n^2 的；这种方法的快排不适合处理这种数据。

代码实现 class Solution { public: void moveZeroes(vector<int>& nums) { int dest = -1,cur = 0; while(cur < nums.size()) { //遇到 0 元素，不做任何处理，cur 向后移一位 if(nums[cur] == 0) { cur++; } else //遇到非 0 元素，dest向后移一位，交换两位置元素，再cur++ { dest++; swap(nums[dest],nums[cur]); cur++; //也可以这样 //swap(nums[dest + 1];nums[cur]); //dest++; //cur++; } } } };

时间复杂度：O(N），空间复杂度：O(1)

【题目二】复写零 题目要求

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。 注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1： 输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2： 输入：arr = [1,2,3] 输出：[1,2,3] 解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示： 1 <= arr.length <= 10^4 0 <= arr[i] <= 9 原题链接

算法原理（思路讲解 + 画图模拟演示）

解法：双指针算法 先根据“异地”操作，然后优化成双指针下的“就地”操作。 这里的 ”异地“ 是指开多一个新的数组进行操作，”就地“ 则是在原数组进行操作。

思路一：" 异地 " 操作，开一个与原数组 arr 大小一样的新数组 tmp，定义一个下标 cur 指向原数组 arr 的第一个位置 ，另一个下标 dest 指向新数组 tmp 第一个位置，遍历 arr 数组，cur 遇到非 0 元素时，将 cur 指向的元素写入新数组 tmp 中 dest 指向的位置，然后cur++, dest++，cur 遇到 0 元素，将 0 写入新数组 tmp 中 dest 指向的位置，dest++,连续操作两次之后，cur++，直到 dest 的值等于 arr 数组的元素个数 n 时停止，最后把 tmp 数组拷贝到原数组 arr 即可。

思路二：" 就地 " 操作，模拟双指针的 ”异地“ 操作，优化成双指针下的 ”就地" 操作； 由于从左向右进行复写时会把后面要写入的数覆盖掉而导致出错，因此，我们需要先找到最后一个要 ”复写“ 的数，然后从后往前完成复写操作。

注意：这里小编所指的 ”复写“ 的数不一定是 0，准确来说是要写入的数，描述有误。 而先找到最后一个要 ”复写“ 的数，怎么找呢？其实也是双指针算法，如下图 找到以后再完成复写操作，如下图：

代码实现

思路一比较简单，这里不过多赘述。

思路二代码如下：

class Solution { public: void duplicateZeros(vector<int>& arr) { //1.先找到最后一个要复写的数 int cur = 0,dest = -1,n = arr.size(); while(cur < n) { if(arr[cur] == 0) dest += 2; else dest++; if(dest >= n - 1) break; cur++; } //2.处理一下边界情况 if(dest == n) { arr[n - 1] = 0; cur--,dest -= 2; } //3.从后向前完成复写操作 while(cur >= 0) { if(arr[cur]) { arr[dest] = arr[cur]; dest--,cur--; } else { arr[dest] = 0; dest--; arr[dest] = 0; dest--; cur--; } } } };

时间复杂度 O(N) ； 空间复杂度 O(1)