移动零:把 0 全部移到末尾
LeetCode 283:给一个数组,把所有 0 移到末尾,同时保持非零元素的相对顺序,而且要原地完成。这道题具备异构指针的三个特征:array 类型、有两类元素(零 / 非零)、它们之间有要维持的顺序。
思路:用两个同向指针。慢指针 j 始终指向「下一个非零元素的写入位置」,快指针 i 向前扫描。每当 i 扫到一个非零数,就把它与 j 处交换,然后 j 前进一格。于是 [0, j) 这段永远是已就位的非零元素(顺序不变),[j, i] 之间则是扫过的零。
尝试默认的 0,1,0,3,12(LeetCode 原例,结果应为 1,3,12,0,0),或换成自己的数组。重点关注两件事:j 只在交换后才前进;当 i === j 时是「与自身交换」,原地不动——这正是数组开头连续一段非零时的情形。
为什么 O(n) 还原地?快指针 i 只前进、永不回退,共走 n 步;慢指针 j 只在「碰到非零」时跟进一格。全程没有额外数组,只在原数组上交换——时间
、空间
。对比一下:先数零、再开新数组搬运,或反复 splice 删 0 再 push,都会退化成
或多占一份空间。
它是 Cyclic Sort 的雏形。「第 k 次遇到非零,就把它换到第 k 个位置」——这种「按出现次序依次归位到前缀」的思路,正是 cyclic sort 的思想:每个元素都有一个确定的目标位置,一趟扫描各就各位。把「非零」换成「值 v 应在下标 v」,同一方法就能解「找缺失的数 / 找重复的数」一类题。同向双指针的另一个经典方向是合并两个有序数组的逆向填充。