LeetCode 热题 100 | 283. 移动零

📝 题目描述

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

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

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

---

💡 核心思路：快慢指针

如何在不复制数组的前提下，原地（In-place）完成操作？这道题是理解“双指针”逻辑的最佳入门教材。

我们定义两个指针 l（慢指针）和 r（快指针）： 1. 慢指针 l：指向“下一个存放非零元素”的位置。 2. 快指针 r：负责向后扫描，寻找数组中的非零元素。

动态演示

当快指针 r 发现一个非零元素时： * 我们将 nums[r] 与 nums[l] 进行交换。 * 交换后，l 向后移动一位，确保它始终指向非零区域的边界。

为什么这个解法很巧妙？

• 稳定性：由于我们是从左往右顺序扫描并交换，非零元素之间的相对顺序被完美保留。
• 零的自然处理：随着 l 的推进，被交换到后面的元素自然而然地形成了“零池”。

---

💻 代码实现 (C++)

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int l = 0; // 慢指针：指向已处理序列的尾部
        int r = 0; // 快指针：指向待处理序列的头部
        
        while(r < n) {
            // 当快指针遇到非零元素时
            if(nums[r] != 0) {
                // 交换快慢指针指向的内容
                if(r > l) {
                    swap(nums[r], nums[l]);
                }
                // 慢指针前进，扩大非零区间
                l++;
            }
            // 快指针始终前进
            r++;
        }
    }
};

📊 复杂度分析

时间复杂度

T(n) = O(n)

我们仅对数组进行了一次遍历，每个元素最多被交换一次。

空间复杂度

S(n) = O(1)

直接在原数组上操作，仅使用了两个整型变量作为指针，满足题目要求的“原地”操作。