【优选算法专栏】专题一：双指针--------1.移动0

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。 通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn

⏩专栏分类：算法从入门到精通

🚚代码仓库：小小unicorn的代码仓库🚚

🌹🌹🌹关注我带你学习编程知识

专题一

• 题目来源
• 题目描述：
• 题目解析
• 算法原理
• 代码实现

  题目来源

  本题来源为：

  Leetcode283:移动零

  题目描述：

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

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

  

  题目解析

  这个题目要实现的其实就是将0移动到后面，

  

  要注意三点：

  1. 0 要移动到数组的末尾
  2. 保持非零元素的相对顺序

     这个怎么理解呢？举个例子：

     

     在这个示例中，未移动前非0元素的顺序为1 3 12，那么移动0之后非0元素也要保持一个1 3 12的顺序。

  3. 不能开辟一个新的数组，要原地操作。

  算法原理

  对于移动0本题来说，是一个很典型的题目，本题还可以规划到数组划分（或者数组分块）这一类。

  什么是数组划分呢？数组划分就是将一个原数组划分为不同区域。

  如下图所示，可以将数组划分为若干个区域，而对于本题而言：

  就是将原数组划分为两个区域：非0元素区间与0元素区间。

  而解决数组划分这一类题，我们最容易想到也是最简单解决的办法----双指针算法。

  

  那么什么是双指针算法呢？

  

  双指针算法就是定义两个指针，通过模拟两个指针的走向来解决问题，化繁为简。但是并不是说双指针就要必须强行定义两个指针，双指针是一个思想，用数组下标也可以来充当指针，定义两个变量也可以充当指针。

  对于本题而言：

  两个指针的作用可以这样定义：

  1. cur：从左往右扫描数组，达到遍历数组
  2. dest:已处理的区间内，非0元素的最后一个位置。

  

  通过双指针我们可以将这个数组分为二大个区间：

  处理过的区间与未处理的区间，在处理过的区间内可以又分成两个区间：非0元素区间与0元素区间。

  不停向后遍历，知道cur遍历完整个数组为止。

  下面我们用具体示例来模拟一下这个过程：

  

  通过动图，我们可以总结双指针式如何做到的：

  在cur从前往后遍历数组时：

  1. 遇到非0元素：cur++
  2. 遇到非0元素：

     先交换dest+1与cur的位置，然后让dest++,cur++;

     注意：dest的起始位置是-1（没进行遍历前还不知道非0元素具体在哪一个位置）。

  代码实现

  class Solution 
  {
  public:
      void moveZeroes(vector& nums) 
      {
         for(int cur=0,dest=-1;cur 
              //处理非0元素
              if(nums[cur])
              {
                  dest++;
                  //交换dest+1与cur的位置
                  swap(nums[dest],nums[cur]);
              }
          }
      }
  };