【算法专题突破】双指针 - 移动零（1）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 移动零（1）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

写在前面

在进行了剑指Offer和LeetCode hot100的毒打之后，

我决心系统地学习一些经典算法，增强我的综合算法能力。

1. 题目解析

题目链接：283. 移动零 - 力扣（Leetcode）

【算法专题突破】双指针 - 移动零（1）,算法专题训练,c++,算法,双指针

读完题目大概就能明白他的意思，

就是在不改变其他数字的情况下，把0都移动到数组最后面去。

2. 算法原理

这道题算是一道数组类的题目，而题目把数组分成了两个区间，

左边是放非0的数，而右边放的是0，

而解决这一类的题目有一个非常经典的算法：双指针算法，

说到双指针算法，难道我们真的要用两个指针来做这道题目吗？

当然不是，双指针只是他的名字，实际上双指针算法指的是：

利用数组下标来充当指针，

那我们如何使用双指针算法来做这道题目呢？

我习惯创建两个变量作为双指针：left 和 right，

1. right 的作用是遍历整个数组

2. left 的作用是作为分界线，左边区间是已经排好的，右边区间是还没排好的

让 right 一直往后走（right++），

如果 right 所在的位置不为 0 ，就交换 left 和 right 位置的值，让 left ++，

因为 left 和 right 的起始位置相同，

这样就能保证当他们开始交换的时候，left 一定待在 0 位置上，而 right 在非 0 位置上。

来我们开始编写代码：

3. 代码编写

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size(), left = 0, right = 0;
        while (right < size) {
            if(nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};