繼第 11 天的「287. Find the Duplicate Number」，今天來解 283 這題！還沒看過第 10 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Easy
• 網址： https://leetcode.com/problems/move-zeroes

演算法與資料結構

• Array
• Pointer

題意

給予一個整數陣列，把所有的 0 移動到陣列的最右側，同時必須維持非 0 數字的排序。

操作過程必須要是 in-place ，不能複製出任何的陣列。

條件

• In place

Follow up

• 如何盡量減少操作

解說

解法還滿直觀的，使用一個 pointer or flag 拿來標記「整理好的」陣列的末端，逐一走訪時，如果遇到非 0 的數字，就和 flag 交換。

範例

Step 1

index: 0
flag: 0

nums[0] == 0 ，跳過不需要執行

 f
[0, 1, 0, 3, 12]
 ^

Step 2

index: 1
flag: 0

 f
[0, 1, 0, 3, 12]
    ^

nums[1] == 1 ，需要和 flag 交換
並將 flag += 1

    f
[1, 0, 0, 3, 12]
    ^

index: 1
flag: 1

Step 3

index: 2
flag: 1

    f
[1, 0, 0, 3, 12]
       ^

nums[2] == 0 ，跳過不需要執行

Step 4

index: 3
flag: 1

    f
[1, 0, 0, 3, 12]
          ^

nums[3] == 3 ，需要和 flag 交換
並將 flag += 1

       f
[1, 3, 0, 0, 12]
          ^

index: 3
flag: 2

Step 3

index: 4
flag: 2

       f
[1, 3, 0, 0, 12]
             ^

nums[4] == 12 ，需要和 flag 交換
並將 flag += 1

           f
[1, 3, 12, 0, 0]
              ^

index: 4
flag: 3

Step 4

index: 5 走訪完畢

這時候就已經走訪完成了：

[1, 3, 12, 0, 0]

程式碼

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var flag = 0
        for index in 0..<nums.count {
            if nums[index] != 0 {
                nums.swapAt(index, flag)
                flag += 1
            }
        }
    }
}

執行結果

• Runtime: 142ms (Beats 92.04%)
• Memory: 15.02MB (Beats 49.58%)

複雜度分析

令 n 為陣列的長度

結語

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！