移动 0

C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2022-02-08

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
        return nums;
        // write code here
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-02-09

class Solution {
public:
    /*
    方法一：两次遍历（笨办法）
    */
    vector<int> moveZeroes1(vector<int>& nums) {
        if(nums.size()== 0) return nums;
        //第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0; i<nums.size(); ++i) {
            if(nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了，剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j; i<nums.size(); ++i) {
            nums[i] = 0;
        }
        return nums;
    }

    /*
    思路同方法一，另一种实现
    将所有 0 移到最后，其实就相当于移除 nums 中的所有 0，然后再把后面的元素都赋值为 0 即可。

    参考：
    https://labuladong.gitee.io/algo/2/21/68/
    */
    vector<int> moveZeroes(vector<int>& nums) {
        // 去除 nums 中的所有 0
        // 返回去除 0 之后的数组长度
        int p = removeElement(nums, 0);
        // 将 p 之后的所有元素赋值为 0
        for (; p < nums.size(); p++) {
            nums[p] = 0;
        }
        return nums;
    }

    /*
    方法二：双指针

    思路及解法
    1. 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
    2. 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

    注意到以下性质：
    1. 左指针左边均为非零数；
    2. 右指针左边直到左指针处均为零。
    因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

    举例：nums=[0,1,0,3,12]
    left=0, right=1, nums=[1,0,0,3,12] <--- 交换 left=1
    left=1, right=3, nums=[1,3,0,0,12] <--- 交换 left=2
    left=2, right=4, nums=[1,3,12,0,0] <--- 交换 left=3，循环结束！

    复杂度分析
    时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。
    空间复杂度：O(1)。只需要常数的空间存放若干变量。
    */
    vector<int> moveZeroes2(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
        return nums;
    }

private:
    // 双指针技巧，复用 [27. 移除元素] 的解法。
    int removeElement(vector<int> &nums, int val) {
        int fast = 0, slow = 0;
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 436KB, 提交时间: 2022-02-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> moveZeroes(vector<int>& nums) {
        // write code here
        vector<int> res;
        int countN = 0;
        for(int i = 0;i < nums.size();i++){
            if(nums[i]!=0){
                countN++;
                res.push_back(nums[i]);
            }
        }
        for(int i = countN;i < nums.size();i++)
            res.push_back(0);
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> moveZeroes(vector<int>& nums) {
        // write code here
        if(nums.size() < 2){
            return nums;
        }
        
        for(int i=0; i < nums.size(); i++){
            if(nums[i] != 0){
                continue;
            }
            for(int j=i+1; j < nums.size(); j++){
                if(nums[j] != 0){
                    swap(nums[i], nums[j]);
                    break;
                }
            }
        }
        
        return nums;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-06-16

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> moveZeroes(vector<int>& nums) {
        // write code here
        int n=nums.size();
        auto i=nums.begin();
        while(n--){
            if(*i==0) {
                nums.erase(i);
                nums.push_back(0);
                i--;
            }
            i++;
        }
        return nums;
    }
};

详情