移动零

题目

给定数组 nums将所有 0 移到末尾。保持非零元素相对顺序，并在原地修改。

思路

暴力想法：开新数组。先装非零元素，再补零，时间 O，但要额外空间 O，不符合“原地”要求。

调整到原地：用快慢指针模拟“分区”操作。

• fast：遍历者，负责“发现”非零元素。
• slow：守门员，指向“下一个非零元素该放的位置”。

每次 fast 发现非零元素。就交换到 slow 位置，接下来 slow 前移。再看这样，

• 我当时卡在这：为什么需要两个指针？怎么避免自己换自己，边界条件怎么处理？按理说，等一系列痛点都在此处得到解答！
  • 为什么需要两个指针？一个指针无法分区，- 一个负责寻找非零，一个负责维护目标位置；不过，单指针无法同时完成搜索与定位，需要有人“守”位置才能保证顺序不乱。
  • 交换 vs 赋值？赋值会覆盖元素，需要两步还是一步？- 直接赋值会把当前位置的值覆盖掉，接下来再补回0；而一次交换可以在一步完成移动并保持剩余结构。
  • 边界调整：当 slow === fast 时怎么办？- 执行一次自我交换是多余的，可加判断跳过从而略微提高性能并避免无意义操作。
  • 空数组、全0、无0三种极端情况怎么办？ - 算法本身通过循环终止条件和索引检查天然兼容，无需额外特殊处理。
  "只要记住三条不变式： 1️⃣。nums] =,nums];按理说，} // 将 next target 向右移动 slow++;} } // 原地修改，无需返回 };
  • 时间这方面。O，一次遍历就可以完成任务。
  • 从空间来看。O，仅使用了两个整型变量作为指针，无额外存储需求。
  • 常数级别的自我交换调整虽对大多数数据无显著影响，但对于极大规模或高频调用场景仍可省略若干 CPU 周期。

  下次看到类似题 → 用快慢指针。一个找元素，一个守位置，partition 思想可迁移至颜色分类、删除元素等场景。🙌  📌  🧠 —— 只要记住这句，“谁找到谁走”，就不会被坑！—- ––– ––– ––– ––– –––

   
  
  · 删除元素类：将等于 val 的 “删除” 移到末尾。· 分区类：三色分类，· 快排 partition 思想迁移。

  -- 第 次复习 • 结果 ：通过 ✅ • 记得牢： ◦ 同向快慢指针。原地修改，无需额外数组 ◦ slow 的含义：下一个非零应该放的位置 ◦ 遇到 nums!其实，== ​ 时就交换到 slow，接下来 slow++ ◦ 时间 O。空间 O • 增加： ◦ 单元素情况细节——fast只遍历一次不是“一直++” ◦ slow === fast 调整未提，下次注意。

  -- 第 次复习 • 结果 ：通过 ✅ • 记得牢： ◦ 双指针思路清晰—s 守位、f 找位、swap一次即可 ◦ 时间 O、空间 O ◦ 边界分析完善—空数组、全0、无0皆能正确处理 ◦ AC代码标准，一步到位 • 增加： ◦ partition 思想联系未提——本质是快排划分，条件改为是否为0

  -- 第 次复习 • 结果 ‑‑通过 ✅ • 记得牢： ◇ 三个区域不变量已讲清楚：[。s) 已归位 非zero 区，[s,f) 零 区，[f,n) 未知 区 ◇ swap vs overwrite 区别明确——overwrite漏 element，还需补齐 zeros ◇ 三种边界情况均对——全 非zero 同步、全 zero f 越界 s 不动、空 arr 不进循环 ◇ AC速度秒 —— 标准代码 • 增加： ◊ partition 思想关联——本质是快排划分，可迁移至颜色分类、移除元素等场景 ◊ slow === fast 调整——跳过自我 swap，虽然微小，却值得记录。

  -- 第 次复习 • 结果 ‑‑毕业 🎓 • 记得牢： ◇ 快慢指针对齐 — s 守 non-zero 边界、f 扫描 —— 完成 swap —— O/O ◇ 三个区域不变量 & swap vs overwrite 区别仍清楚

  ● 增加

  - slow === fast 调整 —— 自己换自己可以跳过不影响正确性，但能省下几条语句。

  - partition 思想关联 —— 本质是快速排序的划分算法。可用于多种模板题目，如颜色分类或删除指定值。

  ---