283. 移动零：动态规划：一样的套路，再求一次完全平方数

力扣题目链接

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

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

思路

做这道题目之前，大家可以做一做27.移除元素

这道题目，使用暴力的解法，可以两层for循环，模拟数组删除元素（也就是向前覆盖）的过程。

好了，我们说一说双指针法，大家如果对双指针还不熟悉，可以看我的这篇总结双指针法：总结篇！。

双指针法在数组移除元素中，可以达到O(n)的时间复杂度，在27.移除元素里已经详细讲解了，那么本题和移除元素其实是一个套路。

相当于对整个数组移除元素0，然后slowIndex之后都是移除元素0的冗余元素，把这些元素都赋值为0就可以了。

如动画所示：

移动零

C++代码如下：

C++
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        // 将slowIndex之后的冗余元素赋值为0
        for (int i = slowIndex; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

其他语言版本

Java
public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
        }
        // 后面的元素全变成 0
        for (int j = slow; j < nums.length; j++) {
            nums[j] = 0;
        }
    }

Python
    def moveZeroes(self, nums: List[int]) -> None:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
        for i in range(slow, len(nums)):
            nums[i] = 0

交换前后变量，避免补零

Python
    def moveZeroes(self, nums: List[int]) -> None:
        slow, fast = 0, 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1 # 保持[0, slow)区间是没有0的
            fast += 1

Go
func moveZeroes(nums []int)  {
    slow := 0
    for fast := 0; fast < len(nums); fast ++ {
        if nums[fast] != 0 {
            temp := nums[slow]
            nums[slow] = nums[fast]
            nums[fast] = temp
            slow++
        }
    }
}

JavaScript
var moveZeroes = function(nums) {
    let slow = 0;
    for(let fast = 0; fast < nums.length; fast++){
        if(nums[fast] != 0){//找到非0的元素
            nums[slow] = nums[fast];//把非0的元素赋值给数组慢指针指向的索引处的值
            slow++;//慢指针向右移动
        }
    }
    // 后面的元素全变成 0
    for(let j = slow; j < nums.length; j++){
        nums[j] = 0;
    }
};

TypeScript
function moveZeroes(nums: number[]): void {
    const length: number = nums.length;
    let slowIndex: number = 0,
        fastIndex: number = 0;
    while (fastIndex < length) {
        if (nums[fastIndex] !== 0) {
            nums[slowIndex++] = nums[fastIndex];
        };
        fastIndex++;
    }
    while (slowIndex < length) {
        nums[slowIndex++] = 0;
    }
};

C
void moveZeroes(int* nums, int numsSize){
    int fastIndex = 0, slowIndex = 0;
    for (; fastIndex < numsSize; fastIndex++) {
        if (nums[fastIndex] != 0) {
            nums[slowIndex++] = nums[fastIndex];
        }
    }

    // 将slowIndex之后的元素变为0
    for (; slowIndex < numsSize; slowIndex++) {
        nums[slowIndex] = 0;
    }
}

Rust
impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut slow = 0;
        for fast in 0..nums.len() {
            if nums[fast] != 0 {
                nums.swap(slow, fast);
                slow += 1;
            }
        }
    }
}

思路​

其他语言版本​

思路

其他语言版本