54. Move Zeroes

読了目安約1分

その他 / LeetCode 283 (Easy) — 0 を順序を保ったまま末尾へ移動する

この章の目次

問題

LeetCode 283. Move Zeroes（Easy / カテゴリ: その他）

整数の配列 nums に含まれる 0 を、すべて末尾に移動する問題です。 0 以外の要素の相対順序は変えません。コピーの配列を作らず、nums を直接書き換えます。

考え方

ヒント 1

「0 を後ろに送る」のではなく「0 以外を前から詰める」と読み替えます。

ヒント 2

書き込み位置の添字 write を 0 から始めます。配列を左から走査し、0 以外を見つけるたびに write の位置と交換して write を 1 進めます。 write より左は常に「0 以外が元の順序で並んでいる」状態に保たれます。

Swift 実装のポイント

シグネチャは func moveZeroes(_ nums: inout [Int]) です。inout 引数への変更は呼び出し元に反映されるので、戻り値はありません。
2 要素の交換は nums.swapAt(write, read) と書けます。同じ添字どうしでも安全です。
for read in 0..<nums.count where nums[read] != 0 { ... } のように、where でループ対象を絞れます。

模範解答

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

計算量: O(n)。