移动零 — 理解读写指针模式 (C++)

Source: Dev.to

问题概述

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

示例

• 输入: [0, 1, 0, 3, 12]
• 输出: [1, 3, 12, 0, 0]

关键直觉

该问题可以使用双指针（读/写）模式来解决：

• rd（读取指针） – 从左到右遍历数组。
• wrt（写入指针） – 标记下一个非零元素应放置的位置。

当 nums[rd] 为非零时，将其与 nums[wrt] 交换并将 wrt 前移。
rd 始终向前移动；wrt 仅在找到非零元素时前移。
所有的零自然会被移到末尾。

解法 (C++)

class Solution {
public:
    void moveZeroes(vector& nums) {
        int wrt = 0, rd = 0;

        while (rd < nums.size()) {
            if (nums[rd] != 0) {
                swap(nums[wrt], nums[rd]);
                ++wrt;
            }
            ++rd;
        }
    }
};

逐步演示示例

考虑 nums = [0, 1, 0, 3, 12]。

循环结束后：

• 所有非零元素按原始顺序位于前部。
• 零已被推到数组末尾。

复杂度分析

• 时间复杂度: O(n) – 每个元素仅检查一次。
• 空间复杂度: O(1) – 只使用了两个整数指针。

收获

• 读/写指针模式是原地数组操作的强大工具。
• 只要专注于正确放置有效元素，“无效”元素（零）就会自动到达它们应在的位置。
• 该模式在许多其他数组问题中也会出现，例如删除元素或压缩数据。
• 掌握它可以简化大量 DSA（数据结构与算法）问题，使代码更简洁、更高效。