与双指针的亲密接触：快与慢的浪漫交错

1.合并两个有序数组

题目传送门

1.1 题目说明

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

示例 1

输入：

• nums1 = [1, 2, 3, 0, 0, 0]
• m = 3
• nums2 = [2, 5, 6]
• n = 3

输出：[1, 2, 2, 3, 5, 6]

解释：需要合并 [1, 2, 3] 和 [2, 5, 6]。合并结果是 [1, 2, 2, 3, 5, 6]，其中斜体加粗标注的是 nums1 中的元素。

示例 2

输入：

• nums1 = [1]
• m = 1
• nums2 = []
• n = 0

输出：[1]

解释：需要合并 [1] 和 []。合并结果是 [1]。

示例 3

输入：

• nums1 = [0]
• m = 0
• nums2 = [1]
• n = 1

输出：[1]

解释：需要合并的数组是 [] 和 [1]。合并结果是 [1]。注意，因为 m = 0，所以 nums1 中没有元素，nums1 中仅存的 0 仅是为了确保合并结果可以顺利存放到 nums1 中。

1.2 题目分析

题目让我们合并两个非递减顺序排列的整数数组nums1和nums2,此外还有两个整数m和n分别表示nums1和nums2中的元素的个数，但是我们的nums1的初始长度是m+n，nums2的初始化长度是n，说白了就是直接将nums2中的数据挪到nums1中去，然后在挪动的过程中进行排序的操作

那么对于这种题型，出现了两个数组，那么我们是否能使用双指针算法呢？ 那么这里说说我的思路哈:

• 先定义两个指针，一个指向nums1的有效数据的尾部（即m-1），另外一个指针指向nums2的末尾(即n-1)
• 我们从nums1的最后一个位置开始进行元素的填充，即从m+n-1这个位置开始
• 我们依次比较nums1和nums2中当前指针指向的元素，将其中较大的元素放到nums1的后面的位置
• 不断地进行两个指针的移动操作，直到其中一个数组的所有元素都被处理完了
• 如果nums2中还存在剩余的元素的话，我们直接将nums2中剩下的部分赋值到nums1中，（这个时候的nums1本身的前面就是已经有序了）

那么思路成立，下面就是我们的代码部分了

1.3代码部分

//nums1的初始长度就是m+n
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
  int p1=m-1;//nums1最后一个有效元素的下标
  int p2=n-1;//nums2最后一个有效元素的下标
  int p=m+n-1;//这个是nums1的总长度的末尾

  //从后往前进行合并操作
  while(p1>=0&&p2>=0)//循环停止的条件，只要两个数组中都存在未处理的元素的话，就可以继续进行合并的执行操作
  {
      //因为给我们的nums1和nums2都是递减的数组，是有序的
      

      //每次比较的时候将两组中大的元素放到p的位置
      if(nums1[p1]>nums2[p2])
      {
          nums1[p]=nums1[p1];
          p1--;
      }
      else
      {
          nums1[p]=nums2[p2];
          p2--;
      }
      p--;//放下一个元素，这里是换位置
  }
  //到这里的话肯定nums1的指针已经是出界了，不满足循环条件了，但是现在nums2hiatus有元素存在的，那么我们就直接将nums2中剩下的的元素直接复制到nums1中
  while(p2>=0)
  {
      nums1[p]=nums2[p2];
      p2--;
      p--;
  }
}

1.4 代码解析

我们先设置好下标为指向位置，就依照我们的这个题的思路那里进行下标设置 然后我们使用这个while循环进行操作 这个while循环的条件是只要我们的两个指针是大于等于0的话就一直进行循环操作，直到出现合并的现象或者是有一个数组的下标变成0了，然后另外一个数组还有元素没有完成迁移

在循环中，我们利用两个下标进行比较的操作 两个数组中元素大的那一个放到nums1的后面 放完之后我们将迁移元素的那个数组的指针往左边移动一位，操作就是指针减减 对于上面的操作存在两种情况，一种是nums1中的那个指针指向的元素大，另一种就是nums2中的元素大了。 进行完上述的操作之后，我们已经让一个元素放到了nums1的末尾了 那么这个末尾的指针就需要向坐进行移动一步的操作了

然后我们出循环 到这里的话就是两种情况，一种就是nums1和nums2合并完成了，还有一种就是nums1的指针小于0了，因为nums1里面的元素已经移动完了，那么此时就是nums2中还存在元素没有进行迁移了 那么我们直接将nums2中剩下的元素放到nums1里面就行了，因为此时nums2中的元素都是比nums1小的元素了

2.移动零

题目传送门

2.1题目说明

给定一个数组 nums，编写一个函数将所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序。

注意： 必须在不复制数组的情况下原地对数组进行操作。

示例 1

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

示例 2

输入：nums = [0] 输出：[0]

2.2题目分析

这类题可以分为数组划分或者叫做数组分块

解决这类题我们首先就想到了双指针算法

这里的指针是利用数组下标来充当指针

因为在数组中我们可以利用下标索引到对应的元素

我们定义的两个指针一个是dest 一个是cur

两个指针的作用

cur:从左往右扫描数组—遍历数组

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

cur在扫描后会将数组分为两个区间，一个是左边，一个是右边，右边就是待处理的区间，左边就是处理过的

然后再cur处理过的左区间，我们的dest在里面又区分了两个区间，左边的就是非0元素，右边的就是0

所以上面会说dest是已处理的区间内，非0元素的最后一个位置

所以这两个指针将整个数组划分为三个部分

三个区间：

[0,dest] [dest+1,cur-1] [cur,n-1]

非0元素 0 待处理

一开始我们让cur指向第一个元素，因为一开始我们没有开始扫描没有非0元素，所以让dest先指向-1下标这个元素

我们先让cur进行从左往右的扫描操作

当我们的cur遇到0元素的时候cur直接向后移动一位就行了

如果我们的cur碰到非0元素的话

先让dest++,然后让cur位置和dest位置的元素进行交换的操作

如何做到cur从前往后遍历的过程中

2.3代码部分

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        for(int cur=0,dest=-1;cur<nums.size();cur++)
        {
            if(nums[cur])//当cur指向的数不等于0的话
            swap(nums[++dest],nums[cur]);//让dest自增1，增完之后正是我想要交换的
        }
    }
};

2.4代码解析

如何做到cur从前往后遍历的过程中

1.遇到0元素：cur++

2.遇到非0元素：swap(dest+1,cur)

dest++,cur++

我们在这个函数里面写入一个for循环，然后循环的条件就是直到cur走完这个数组就结束，那么只要这个cur的大小小于这个数组的元素我们就能进行循环操作 通过cur遍历整个数组，只要我们的cur指向的元素不是0的话，我们就进行条件语句，先将dest进行++操作，然后我们将dest指向的元素和cur指向的元素进行交换的操作然后这么0就到后面去了，非0元素就在前面了