leetcode283. 移动零-Toy模板网

这篇具有很好参考价值的文章主要介绍了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;  // 记录删掉了几个0
        for(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);
        }
    }
};

运行结果：

leetcode283. 移动零,LeetCode,算法

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

leetcode283. 移动零,LeetCode,算法

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++;
        }
    }
};

它的思路：

leetcode283. 移动零,LeetCode,算法