算法讲解-移动零

一,题目描述

二,算法原理

本题中要求给所有的零移动到数组末尾。相当于给数组划分区间。一部分是非零区间；一部分是零区间。针对区间问题通用的解法--双指针法。如图：

 

首先需要两个下标：

1，第一个下标负责分组[0,d]，[d+1,c-1]。前者区间是非零数据，后者零数据的区间。

2，第二个下标负责分组有没有扫描数据[0，c-1]，[c，数据末尾]。前者表示扫描过的数据，后者表示没有扫描。

从第一个数据开始扫描，若是非零数据，d加加。扫描位置的数据与d的位置进行交换。若是零，则d位置不变，c继续扫描数据。知道数组结束。分组结束。

具体例子：

d最开始没有进行分组，c从第一个位置开始扫描数据，第一个为0，d不变，c加加，继续扫描。

第二个位置数据位置，d加加。之后与c的位置进行交换。如图：

第三个位置数据为0，d不变，c加加扫描数据。

第四个位置数据为3不为零，d加加，与c位置的数据交换。如图：

 

第五个位置数据为12不为零，d加加，与c位置数据交换。如图：

 

c到数组末尾，扫描结束，分组结束。

三,代码实现

void moveZeroes(vector<int>& nums) {int dest = -1;int cur = 0;for(int i = 0 ; i < nums.size(); i++){if(nums[i] != 0){dest++;swap(nums[dest],nums[i]);}}}

四,练习

通过如下链接可以进行此题的练习：

283. 移动零 - 力扣（LeetCode）