解題說明
Move Zeroes
題目描述:給定整數陣列 nums,將所有 0 移至末尾,同時保持非零元素的相對順序,且需原地操作。
解題思路:使用雙指標:慢指標 slow 指向下一個可放置非零元素的位置,快指標 fast 掃描整個陣列。每遇到非零元素,就將其放到 slow 位置並將 slow 前進。最後將 slow 之後的位置全部填 0。整個過程只需一次線性掃描,空間複雜度 O(1)。
C++ 解法
複雜度分析
時間複雜度:O(n) — 快指標遍歷一次陣列,慢指標最多也走 n 步。
空間複雜度:O(1) — 原地操作,不需額外陣列。
虛擬碼
1. Initialize slow = 0
2. For fast from 0 to n-1:
a. If nums[fast] != 0:
- nums[slow] = nums[fast]
- slow++
3. While slow < n:
a. nums[slow] = 0
b. slow++
4. Return (in-place modification)其他解法
交換法(Swap):遇到非零元素時直接與 slow 位置交換,省去最後補零的步驟。swap(nums[slow++], nums[fast]);寫法更簡潔但每次都會做交換,若非零元素很多時寫操作略多。
兩次掃描:先把非零元素複製到新陣列,再寫回原陣列並補零。邏輯清晰但需要 O(n) 額外空間,不符合原地要求。
延伸思考
- 如何在盡量減少寫入次數的前提下完成(即減少對
0的重複覆寫)? - 若要將所有非零元素移至末尾(反向需求),雙指標如何調整?
- 此題與「Remove Element」(LC 27) 的解法有何異同?