給定整數陣列
nums，將所有0移到陣列末尾，同時保持非零元素的相對順序。必須原地操作。
Example:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]
Intuition
TIP
核心思路：用一個慢指針記錄下一個非零元素該放的位置，快指針掃描所有元素。
- 類似「移除特定元素」的模式（LC 27 Remove Element）
- 慢指針維護「已處理區域」的尾端，快指針不斷找非零元素往前搬
- 最後慢指針之後的位置全部填 0
Approaches
1. Extra Array — O(n) / O(n)
- Idea: 建立新陣列，先放非零元素，再補 0
- Time:
O(n) - Space:
O(n)
Extra Array Code
class Solution {
fun moveZeroes(nums: IntArray): Unit {
val result = IntArray(nums.size)
var idx = 0
for (num in nums) {
if (num != 0) result[idx++] = num
}
for (i in nums.indices) nums[i] = result[i]
}
}⭐ 2. Two Pointers (Fast & Slow) — O(n) / O(1)
- Idea: 慢指針
slow追蹤下一個非零元素的位置，快指針fast掃描整個陣列，遇到非零就交換到 slow 位置 - Time:
O(n)- 一次遍歷 - Space:
O(1)- 原地操作
class Solution {
fun moveZeroes(nums: IntArray): Unit {
var slow = 0
for (fast in nums.indices) {
if (nums[fast] != 0) {
val temp = nums[slow]
nums[slow] = nums[fast]
nums[fast] = temp
slow++
}
}
}
}WARNING
使用交換而非覆蓋（先寫非零再補零），可以在一次遍歷中完成，不需要第二次迴圈填零。
🔑 Takeaways
- Pattern: 快慢指針分區（類似 partition），慢指針維護「已處理」邊界
- Key trick: 與 LC 27 Remove Element 同一模板；交換比覆蓋更優雅，一次遍歷搞定