【LeetCode】283. Move Zeroes 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
  2. 解答2：Python
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は次の問題へ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

0を配列の後ろに移動させます。
移動のさせ方によって速さが変わります。
インプレイス処理で行います。

この記事で得られること

初歩的な空間計算量の内容

この記事が役立ちそうな方

空間計算量について知りたい方

詳細

問題

原文

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.

Example 1:

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

1
2

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

Example 2:

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

1
2

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

Constraints:

1 <= nums.length <= 10⁴

-2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Could you minimize the total number of operations done?

内容(和訳)

整数配列arrが与えられるので、0以外の要素の相対的な順序を維持しながら、全ての0を配列の最後に移動させてください。

配列をコピーせずに、インプレイス(元の配列に上書きする形で)実行してください。

※正しくない可能性があります。

解答

解答1：Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        move_count = 0
        for i in range(len(nums)):
            if nums[i-move_count] == 0:
                nums.append(nums.pop(i-move_count))
                move_count += 1

class Solution:

def moveZeroes(self, nums: List[int]) -> None:

"""

Do not return anything, modify nums in-place instead.

"""

move_count = 0

for i in range(len(nums)):

if nums[i-move_count] == 0:

nums.append(nums.pop(i-move_count))

move_count += 1

i番目の要素が0の時に後ろに移動させます。

この時、移動させた回数move_countに記録しておき、iから引き算しています。

i番目の0を後ろに移動させると、配列の並びが変わってしまい、

次のループ(i+1番目)で0を逃す可能性があるからです。

イメージ↓

・i=1　※2番目の要素の0を後ろに移動

[1,0,0,3,4]

・i=2　※配列の並びが変わり、3番目の要素が0から3に変わった。

[1,0,3,4,0]

インプレイス処理について。

本当は新しい配列を作って、0ではない要素を先に追加し、0だけが残った配列を後ろから結合するような方法などを使うとコードを書くとき員は自分は楽だと感じます。

しかし、配列を新しく作ったり、配列をコピーすると、numsの要素と同じだけのメモリが必要になります。

私たちが普段使っているパソコンやスマホはメモリが大きくなっており、記憶容量もたくさん持っているのですが、機械の一部品として使用されるような小さなものには、パソコンやスマホほどにはメモリを持たないものもあるようです。組み込み機器などにはC言語を使うこともあるというような話を時折聞きます。

インプレイス処理はメモリを余分に使用しない、空間計算量を節約したいときに考える必要がある処理だと理解しています。

変数を1つ用意するだけならO(1)、

n個の要素を持つ配列をコピーするなら、O(n)の計算量になります。

※計算量の話は自信がないので、ご自身でも調べてみてください。

解答2：Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        #0のインデックスを持つ変数
        zero = 0
        #numsを一巡して走査
        for i in range(len(nums)):
            print(zero)
            #i番目の要素が0以外の場合
            if nums[i] != 0:
                #i番目の要素と、zero番目の要素(配列内の最初の0の位置)を入れ替える
                #0が出現するまでは、nums[i]とnums[zero]は同じ要素なので入れ替わりは起こらない
                #最初の0が出現し、その次以降の要素で0以外だったときに初めて入れ替わりが起こる
                nums[i], nums[zero] = nums[zero], nums[i]
                #zeroのインデックスを一つ進める
                zero += 1
                print(nums)

class Solution:

def moveZeroes(self, nums: List[int]) -> None:

"""

Do not return anything, modify nums in-place instead.

"""

#0のインデックスを持つ変数

zero = 0

#numsを一巡して走査

for i in range(len(nums)):

print(zero)

#i番目の要素が0以外の場合

if nums[i] != 0:

#i番目の要素と、zero番目の要素(配列内の最初の0の位置)を入れ替える

#0が出現するまでは、nums[i]とnums[zero]は同じ要素なので入れ替わりは起こらない

#最初の0が出現し、その次以降の要素で0以外だったときに初めて入れ替わりが起こる

nums[i], nums[zero] = nums[zero], nums[i]

#zeroのインデックスを一つ進める

zero += 1

print(nums)

こちらは、i番目の要素が0以外の時に操作します。

配列内の最初の0の位置を覚えておき、i番目の要素が0以外の時に、最初の0とi番目の要素を入れ替えます。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は次の問題へ

前：1588. Sum of All Odd Length Subarrays

次：1672. Richest Customer Wealth

LeetCode 解答・解説記事一覧