题目链接： https://leetcode.cn/problems/move-zeroes/

LeetCode 283.移动零

题目描述

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

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

举个例子：

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

思路解析

题目要求对数组原地操作，也就是要求空间复杂度为O(1)。

我们可以遍历一遍数组统计出非零的个数m，然后再遍历一遍数组把非零的元素依次覆盖数组的前m个位置，最后把剩下的n-m个位置置为0。这样我们需要遍历两遍数组，时间复杂度也是O(1)。

下面我再介绍一种只遍历一遍数组的双指针解法，整体的思路类似快速排序。

定义两个指针，left = 0, right = 0。

1. 如果nums[right] == 0，right指针就往右移一步。
2. 如果nums[right] != 0，就交换nums[left]和nums[right]的值，left和right同时向右移一步。

上述步骤保证了left != right时，left始终指向为零的元素，一旦right指向了非零元素，left和right就交换指向的元素。

c++代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for (int right = 0; right < nums.size(); ++right) {
            //right指向元素不为0时，跟left交换指向的元素
            //如果left != right，left一定指向为零的元素
            //就算left == right，交换一下元素也没关系
            if (nums[right]) {
                //交换left和right指向的元素
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                ++left;
            }
        }

    }
};

java代码

class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        for (int right = 0; right < nums.length; ++right) {
            //right指向元素不为0时，跟left交换指向的元素
            //如果left != right，left一定指向为零的元素
            //就算left == right，交换一下元素也没关系
            if (nums[right] != 0) {
                //交换left和right指向的元素
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                ++left;
            }
        }
    }
}

python代码

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
        for right in range(len(nums)):
            #right指向元素不为0时，跟left交换指向的元素
            #如果left != right，left一定指向为零的元素
            #就算left == right，交换一下元素也没关系
            if nums[right] != 0:
                #交换left和right指向的元素
                nums[left], nums[right] = nums[right], nums[left]
                left += 1

复杂度分析

时间复杂度: O(n），其中n为nums的长度。

空间复杂度： O(1)。