leetcode283. 移动零

难度：简单题

题目

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

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

思路：

一开始想，从前往后遍历，遇到0就挪到最后。类似于冒泡的思想，但是这样做的话时间复杂度可能是 三次方。

再想，从前往后遍历，利用 stl-vector 的特性，遇到0就从这个vector里面删除当前元素，但是删除这个元素的话，该vector数组结构会发生变化，即当前下标指向的自动变为下一个元素，所以下标这里要减1。

代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {// 要保持非零元素的相对顺序，不能排序！// 依次遍历，遇到0元素，则用冒泡排序的思想挪到最后 时间复杂度 三次方？？// 思路，依次遍历，如果遇到0，则从vector中删掉该元素，并记录删了几个，最后添上去// 遍历时删元素会不会使数组下标发生变化？会使数组结构发生变化！int i = 0;int n = 0;  // 记录删掉了几个0for(i = 0; i < nums.size(); i++){if(nums[i] == 0){nums.erase(nums.begin()+i);n++;i--;    // 删掉当前元素，数组会立即发生变化！}}// 删了几个元素，后面补几个0        for(i = 0; i < n; i++){nums.push_back(0);}}
};

运行结果：

好吧，看了一下官方双指针代码，它的效果要好一点。。

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

 它的思路：