题目描述

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

样例

输入：[0,1,0,3,12]
输出：[1,3,12,0,0]

说明

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

算法

(双指针) $O(n)$

1. 设 i 表示当前访问到的位置，j 表示当前第一个可以放置非零元素的位置。
2. i 每次向后移动时，如果 nums[i] != 0，则将 nums[j] 赋值为 nums[i]，同时 j++。
3. 最后将 j 到末尾的所有元素赋 0。

时间复杂度

• 每个位置仅被遍历和赋值各一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅使用常数的额外空间。

C++ 代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for (int i = 0; i < n; i++)
            if (nums[i] != 0)
                nums[j++] = nums[i];

        for (; j < nums.size(); j++)
            nums[j] = 0;
    }
};