Easy

题目描述

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

注意 必须在原地对数组进行操作，不能拷贝额外的数组。

示例 1:

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

示例 2:

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

约束条件:

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

进阶： 你能尽量减少完成的操作次数吗？

提示：

  • 原地 意味着我们不应该为额外的数组分配空间。但我们被允许修改现有数组。不过，作为第一步，尝试想出一个使用额外空间的解决方案。对于这个问题，首先应用使用额外数组讨论的思想，原地解决方案最终会出现。
  • 双指针 方法在这里可能很有帮助。思路是用一个指针遍历数组，另一个指针只处理数组的非零元素。

解题思路

这道题要求将数组中的所有零移动到末尾，同时保持非零元素的相对顺序，且要求原地操作。

解题思路：

最直观的思路是使用额外数组，先收集所有非零元素，再在末尾补零。但题目要求原地操作，所以需要更优雅的解法。

最优解法 - 双指针法： 使用两个指针，slow 指向下一个非零元素应该放置的位置，fast 用于遍历数组。当 fast 遇到非零元素时，将其与 slow 位置的元素交换，然后 slow 向前移动。这样可以保证所有非零元素都被移到前面，且保持相对顺序。

其他解法：

  1. 移除填充法： 先移除所有零，再在末尾填充相应数量的零
  2. 冒泡法： 类似冒泡排序，将零逐个"冒泡"到末尾

双指针法最优，时间复杂度 O(n)，空间复杂度 O(1)，且操作次数最少。

代码实现

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            if (nums[fast] != 0) {
                swap(nums[slow], nums[fast]);
                slow++;
            }
        }
    }
};

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

public class Solution {
    public void MoveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.Length; fast++) {
            if (nums[fast] != 0) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let slow = 0;
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
            slow++;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 为数组长度。算法只需要遍历数组一次，每个元素最多被交换一次，所以时间复杂度为 O(n)。只使用了常数个额外变量，空间复杂度为 O(1)。

相关题目