LeetCode-移动零

一、题目描述

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

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

示例 1:

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

示例 2:

输入: nums = [0]
输出: 
[0]

二、解题思路

题目要求必须原地操作，不能复制数组。比如示例里的数组是[0,1,0,3,12]，处理后变[1,3,12,0,0]。

看起来非零元素的顺序要保持不变，然后把零都放到后面。

可能的一个思路是，用双指针的方法。比如，一个指针用来遍历数组，另一个指针记录当前非零元

素应该放的位置。然后每次遇到非零元素，就把它放到前面的位置，最后剩下的位置补零。初始化

一个指针j=0。然后遍历数组，当遇到nums[i]不等于零的时候，就把nums[j]设置为nums[i]，然后j

加一。这样遍历完一遍之后，所有非零元素都被移到了前面，顺序不变。之后剩下的位置j到末尾

都设置为零。这个方法应该可行，而且时间复杂度是O(n)，空间复杂度是O(1)，符合要求。

如例子中的第一个例子，遍历的时候，i从0开始。当i=0的时候，元素是0，跳过。i=1的时候元素是

1，放到nums[0]，j变成1。i=2的时候是0，跳过。i=3的时候是3，放到nums[1]，j变成2。i=4的时

候是12，放到nums[2]，j变成3。然后遍历结束后，从j=3的位置开始，将后面的元素都设为0。所

以原数组被修改为1,3,12,0,0，符合要求。

原数组是[1,2,3,0,4]。处理过程：

i=0，nums[i]=1，赋值给j=0，j=1。

i=1，nums[i]=2，赋值给j=1，j=2。

i=2，nums[i]=3，赋值给j=2，j=3。

i=3，nums[i]=0，跳过。

i=4，nums[i]=4，赋值给j=3，j=4。

遍历结束后，j=4，此时n=5，所以剩下的位置是4到4，即nums[4]=0。这时候数组变成了

[1,2,3,4,0]。原来的那个0在索引3的位置，已经被覆盖了，原来的数组中的4被移动到了索引3的位

置，然后索引4的位置被置零。

原问题要求将所有零移动到末尾，非零元素的相对顺序不变。原来的数组中的零是位于索引3的位

置，处理后，数组是[1,2,3,4,0]，这样确实符合要求。那这个方法是可行的。比如原来的4在索引4

的位置，现在被移动到了索引3的位置，后面被置零。当i=4的时候，此时j=3，所以nums[3]=4，而

原来的nums[3]是0，所以没有问题。然后遍历结束后，将j=4的位置置零，即nums[4]=0。这样处

理后的结果是正确的。

三、大致步骤

1. 初始化j=0。

2. 遍历数组，i从0到n-1。

3. 如果nums[i]不等于0，就将nums[j] = nums[i]，然后j自增。

4. 遍历结束后，将j到n-1的位置都置为0。

想到这里，假设数组是[1,0,2,0,3]，当i=0时，nums[j=0]=1，j=1。i=1的时候是0，跳过。i=2的时候

是2，此时j=1，所以nums[1]=2，j=2。这样原来的nums[1]的0就被覆盖了。但这样没问题，因为之

后会把后面的位置都置零。 所以这个方法是可行的。

要解决将数组中的所有零移动到末尾并保持非零元素顺序的问题，可以使用双指针方法。具体思路

是遍历数组，将非零元素依次移到数组前面，然后将剩余位置填充为零。这种方法确保了原地操作

且时间复杂度为O(n)。

四、方法思路

1. 双指针遍历 ：使用指针 j 来记录当前非零元素应放置的位置。遍历数组，当遇到非零元素时，将其移到 j 的位置，并递增 j 。
2. 填充零 ：遍历结束后，所有非零元素已移到数组前面，剩余位置从 j 开始填充零。

五、解决代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j = 0;
        // 将非零元素移动到数组前面
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        // 将剩余位置填充为零
        while (j < nums.size()) {
            nums[j++] = 0;
        }
    }
};

以上就是，这道题的全解啦！！！！关注博主，持续分享力扣算法题。