LeetCode 283. Move Zeroes

はじめに

LeetCode 「283. Move Zeroes」の問題をGoで解きました。

問題

https://leetcode.com/problems/move-zeroes/description/

問題文

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.

和訳
整数配列 nums が与えられたとき、0 以外の要素の相対順序を維持したまま、すべての 0 を配列の末尾に移動する。
配列のコピーを作成せずに、インプレースで行う必要があることに注意してください。

例

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Input: nums = [0]
Output: [0]

制約

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

解答1（Two Pointers）

思いついたのでは、Two Pointers パターンでの実装です。
Two Pointers パターンは2つの位置からポインタを動かして探索を行う方法です。

今回はインプレースで行う必要もあることから、0以外の要素が来るべきインデックスを記録しておき、0以外の要素であればスワップを行うことで実現できそうです。

コード

func moveZeroes(nums []int)  {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

• slow: 0以外の要素を置くべき位置
• fast: ゼロ以外の要素を探すポインタ

fastが0の場合は、slowは動かないので、slowは常に0以外の要素を置くべき位置になります。
0以外の要素の時に位置をスワップすることで、最終的に0が後ろに集まります。

補足

最初の要素が0以外の場合など、fastとslowが同じ数字の時に、不要なスワップが発生することがあります。
if slow != fastの条件を追加すれば、不要なスワップは防ぐことが可能です。
ただし、以下の理由から条件の追加はしなくてもよいと思いました。

• スワップのコストは小さい
• 条件を追加すると全ループで条件チェックが発生し、スワップよりもそのコストが大きい可能性もある
• コードがシンプルになる

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)

解答2（左詰め）

別のアプローチもあったので紹介します。
左詰めし、最後に0を埋めていくパターンです。

コード

func moveZeroes(nums []int)  {
    count := 0
    for _, num := range nums {
        if num != 0 {
            nums[count] = num
            count++
        }
    }

    for i := count; i < len(nums); i++ {
        nums[i] = 0
    }
}

countは0以外の要素をカウントしています。
0以外の要素を左詰めしていきながらカウントし、カウントを元に後の要素を0に置き換えています。

Two Pointersのパターンと比べると、0で埋める分配列の変更回数が多くなります。
大きなデータセットでは効率が悪くなる可能性があるため、Two Pointersのパターンの方が実用的と言えます。

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)