LC283
移动零
数组写游标 · 快慢指针可视化:数组写游标给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
两个指针都从数组开头出发
正在加载算法场景...
当前发生了什么
给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。
机器状态
非零写位 slow、扫描指针 fast、已就位非零个数。
为什么正确
slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。
不变量
下标区间 [0, slow) 是已就位的非零元素,保持相对顺序。
面试怎么说
我用快慢指针:slow 是非零写位,fast 扫描,遇到非零就和 slow 交换并前移 slow;一趟完成,非零保序、零自然沉底,O(n)/O(1)。
人类输入
给定数组 [0,1,0,3,2],原地把所有 0 移到末尾,保持非零元素的相对顺序。
机制
slow 指向下一个非零应放的位置;fast 扫描,遇到非零就与 slow 交换并前移 slow。
机器状态
非零写位 slow、扫描指针 fast、已就位非零个数。
可观察结果
数组变为 [1,3,2,0,0],非零在前且保持原序,零在末尾。
不变量
- · 下标区间 [0, slow) 是已就位的非零元素,保持相对顺序。
- · 下标区间 [slow, fast) 全为 0。
常见误区
- · 用「先覆盖再补零」两趟也行,但交换法一趟完成且天然保序。
迁移练习
- · LC27 移除元素
- · LC26 有序数组去重
面试怎么答
我用快慢指针:slow 是非零写位,fast 扫描,遇到非零就和 slow 交换并前移 slow;一趟完成,非零保序、零自然沉底,O(n)/O(1)。