ゼロから始めるLeetCode Day15 「283. Move Zeroes」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day14 「136. Single Number」
次回
ゼロから始めるLeetCode Day16 「344. Reverse String」

問題

283. Move Zeroes

難易度はeasy。
今回もTop 100 Liked Questionsからの抜粋です。

問題としては、配列が与えられ、その中の全ての要素を舐めていき、もし値が0だった場合、その0を末尾に挿入します。なお、その際に0以外の値の要素の順序はそのまま保たなければなりません、という問題です。

Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

解法

二通りの考えが思い浮かんだのでその片方を実装してみました。
片方は0を動かす考え方、そしてもう一方は0以外の数値を動かす、という方法です。
まずは前者を実装してみました。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(1,len(nums)+1):
            if nums[-i] == 0:
                nums.pop(-i)
                nums.append(0)
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

popとappendで要素の削除と末尾への挿入を行っています。

対して後者は以下のように実装しました。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        h = -1
        for i in range(len(nums)):
            if nums[i] != 0:
                h += 1
                nums[h], nums[i] = nums[i], nums[h]
# Runtime: 52 ms, faster than 54.28% of Python3 online submissions for Move Zeroes.
# Memory Usage: 15 MB, less than 5.97% of Python3 online submissions for Move Zeroes.

まず、hに-1を代入し、iに要素数を代入します。そして仮にnums[i]が0ではない場合、hに1を足し、nums[h]にnums[i]をnums[h]をnums[i]に代入することで入れ替えることがきます。
結果的にこれを全てのように対して行うことで全ての0以外の値が順番を乱すことなく先頭にソートされます。

今回は二つの手順で考えてみました。
もっと良い考え方があれば追記します。