283. 移动零

题目描述

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

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

示例 1:
输入: nums = [0,1,0,3,12]
输出:[1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

思路

方法一

可以使用双指针来解决该问题。题目描述需要在所有数字之后补0，那么我们可以定义一个变量 temp_num 来记录并且保存当前数字的下标，再用变量 i 来表示数字的下标和0.
时间复杂度为O(n)
空间复杂度O(1)

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //记录原来数组的长度
        int len = nums.size();
        int temp_num = 0;
        //保存非0的数字
        for(int i = 0; i < len; i++){
            if(nums[i] != 0)
                nums[temp_num++] = nums[i];
        }
        //在非0的数字后面补0
        for(int i = temp_num; i < len; i++){
            nums[temp_num++] = 0;
        }
    }
};

方法二

直接使用暴力法来遍历

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0){
                for(int j = i + 1; j < nums.size(); j++){
                    if(nums[j] == 0)
                        continue;
                    //交换两个数
                    else{
                        int temp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                }
            }
        }
    }
};