目录

移动零

题目解析

讲解算法原理

编写代码

复写零

题目解析

讲解算法原理

编写代码

---

移动零（easy）

题目解析

「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个数组 nums ，编写⼀个函数将所有 0 移动到数组的末尾，同时保持⾮零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进⾏操作。⽰例1:
输⼊: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
⽰例2:
输⼊: nums = [0]

输出: [0]

3.解法（快排的思想：数组划分区间-数组分两块）：

讲解算法原理

算法思路：
在本题中，我们可以⽤⼀个 cur 指针来扫描整个数组，另⼀个 dest 指针⽤来记录⾮零数序列的最后⼀个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
在 cur 遍历期间，使 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零。

算法流程：

a. 初始化 cur = 0 （⽤来遍历数组）， dest = -1 （指向⾮零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1 ）

b. cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：

        i. 遇到的元素是 0 ， cur 直接 ++ 。因为我们的⽬标是让 [dest + 1, cur - 1] 内的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1 的位置上，从⽽在 [dest + 1, cur - 1] 内；

        ii. 遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让cur++ ，扫描下⼀个元素。

                • 因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 ；

                • dest++ 之后，指向的元素就是 0 元素（因为⾮零元素区间末尾的后⼀个元素就是0 ），因此可以交换到 cur 所处的位置上，实现 [0, dest] 的元素全部都是⾮零元素， [dest + 1, cur - 1] 的元素全是零。

两个指针的作用：

cur：从左往右扫描代码，遍历数组

dest：已处理的区间内，非零元素的最后一个位置

编写代码

c++算法代码：

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

算法总结

这个⽅法是往后我们学习「快排算法」的时候，「数据划分」过程的重要⼀步。如果将快排算法拆解的话，这⼀段⼩代码就是实现快排算法的「核⼼步骤」。

复写零（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个⻓度固定的整数数组 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]

3.解法：（原地复写-双指针）： 

讲解算法原理

算法思路：
如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：
i. 先找到最后⼀个复写的数；
ii. 然后从后向前进⾏复写操作。
算法流程：
a. 初始化两个指针 cur = 0 ， dest = 0 ；
b. 找到最后⼀个复写的数：
        i. 当 cur < n 的时候，⼀直执⾏下⾯循环：
                • 判断 cur 位置的元素:
                        ◦ 如果是 0 的话， dest 往后移动两位；
                        ◦ 否则， dest 往后移动⼀位。
                • 判断 dest 时候已经到结束位置，如果结束就终⽌循环；• 如果没有结束， cur++ ，继续判断。
c. 判断 dest 是否越界到 n 的位置：
        i. 如果越界，执⾏下⾯三步：
                1. n - 1 位置的值修改成 0 ；
                2. cur 向移动⼀步；

                3. dest 向前移动两步。
d. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
        i. 判断 cur 位置的值：
                1. 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；2. 如果⾮零： dest 位置修改成 0 ， dest -= 1 ；
        ii. cur-- ，复写下⼀个位置。

编写代码

class Solution
{
public:
 void duplicateZeros(vector<int>& arr) 
 {
 // 1. 先找到最后⼀个数
 int cur = 0, dest = -1, n = arr.size();
 while(cur < n)
 {
 if(arr[cur]) dest++;
 else dest += 2;
 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--];
 else
 {
 arr[dest--] = 0;
 arr[dest--] = 0;
 cur--;
 }
 }
 }
};