Move Zeroes
整数の配列 nums が与えられます。すべての 0 を配列の末尾に移動し、その他の値は元の順序のままにしてください。並べ替えた配列を返してください。配列の長さは nums と同じです。
関数
- numsinteger-array
- 並べ替える整数の配列
- 戻り値integer-array
- 0 以外の値を元の順序のまま先に並べ、すべての 0 を末尾に配置する
制約
1 ≤ nums.length ≤ 5000-105 ≤ nums[i] ≤ 105
例
- 入力
- nums = [0, 4, 0, 7, 2]
- 出力
- [4, 7, 2, 0, 0]
- 説明
- 0ではない値は4、7、2で、先頭にその順序のまま並びます。2つの0は最後の2つの場所を埋めます。
- 入力
- nums = [-3, 8, 1]
- 出力
- [-3, 8, 1]
- 説明
- 移動する 0 がないため、配列は変更されずに戻ります。-3 は負の数であり、ゼロではないため、先頭のままです。
- 入力
- nums = [0]
- 出力
- [0]
- 説明
- 0 を 1 つだけ含む配列は、すでに完成形です。
提出時に隠しテスト+14件
発展問題
代わりに、他の値の順序を保ったまま、すべての0を先頭に移動できますか？追加メモリO(1)で、1回の走査で実現できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
完成した配列をイメージしてください。ゼロ以外の値は元の順序のまま並び、その後にゼロが続きます。最初に出会うゼロ以外の値は、最終的にどこに配置されるべきでしょうか？
先頭にある次の空き位置を示すインデックス
writeを保持します。見つけたゼロ以外の値はすべてその位置に置き、その後、位置を右に1つ移動します。- 2つ目のインデックス
readを使って進めます。nums[read]が0でない場合は、nums[write]と入れ替えて、writeを前に進めます。2つのインデックスの間は常に0なので、入れ替えるたびに0が後ろへ移動し、ほかの値は順序を保ちます。
解説
ゼロを末尾に移動することは難しくありません。難しいのは、ほかの値を元の順序のまま保つことで、そのためには各 0 を最後の要素と入れ替える方法は使えません。配列を、これまでに見つかったゼロ以外の値を保持する先頭領域と、それ以外の部分に分けます。一つのインデックスですべての要素を読み取り、もう一つのインデックスで次のゼロ以外の値を置く位置を示せば、1 回の走査でその場で処理を完了できます。
ゼロ以外の値をコピーする
考え方
新しい配列を作成します。numsを順に確認し、0でない値を、見つけた順にすべてコピーします。次に、新しい配列がnumsと同じ長さになるまで0を追加します。追加する0の数は、スキップした要素の数です。
[0, 4, 0, 7, 2]の場合、コピーする段階で[4, 7, 2]となり、0を2つ追加すると[4, 7, 2, 0, 0]になります。値を読み取った順にコピーするため、順序は正しく保たれます。
各要素は1回読み取られ、1回書き込まれるため、時間計算量はO(n)です。2つ目の配列にはO(n)のメモリが必要ですが、次の方法ではそれを避けられます。
アルゴリズム
- 空の結果配列を作成します。
numsの各値について、0でなければ結果に追加します。- 結果の要素数が
numsと同じになるまで、0を追加します。 - 結果を返します。
def moveZeroes(nums):
result = [x for x in nums if x != 0]
result += [0] * (len(nums) - len(result))
return result2つのポインターによるインプレース交換
考え方
2つのインデックスを使います。readは左から右へ、すべての要素を調べます。writeは、次の非ゼロ値を置く位置を示します。各ステップの後、次の2つが成り立ちます。writeより前には、これまでに見つかった非ゼロ値が元の順序で並び、writeからreadまでの範囲には0が並びます。
nums[read]が0でない場合、それをnums[write]と交換し、writeを1つ右に進めます。readに移動してくる値は、0の領域にあった0か、2つのインデックスが等しい場合は同じ値です。非ゼロ値は0だけを飛び越え、互いを追い越すことはないため、順序は保たれます。
[0, 4, 0, 7, 2]の場合：インデックス1の4をインデックス0と交換すると、[4, 0, 0, 7, 2]になります。インデックス3の7をインデックス1と交換すると、[4, 7, 0, 0, 2]になります。インデックス4の2をインデックス2と交換すると、[4, 7, 2, 0, 0]になります。1回の走査で済み、2つ目の配列も不要です。時間計算量はO(n)、メモリ計算量はO(1)です。
アルゴリズム
writeを 0 に設定します。readを最初のインデックスから最後のインデックスまで移動します。nums[read]が 0 でない場合、nums[read]とnums[write]を入れ替えてから、writeに 1 を加えます。numsを返します。
def moveZeroes(nums):
write = 0 # nums[:write] holds the non-zero values found so far, in order
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
return nums
落とし穴と境界ケース
よくあるバグは、他の値の順序を崩したり、要素を飛ばしたりします。
- 各 0 を最後の要素と入れ替えると、0 は移動しますが、残りの順序が崩れます。
[0, 4, 7]は[7, 4, 0]になります。 - インデックスを進めながら配列から 0 を削除すると、要素を飛ばしてしまいます。
[0, 0, 5]では、インデックス 0 を削除すると、2 つ目の 0 がインデックス 0 に移動しますが、ループはインデックス 1 に進みます。削除するたびに配列の残りの要素もずれるため、ループの計算量は O(n²) になります。 x > 0ではなく、x != 0をテストします。負の値は 0 ではありません。[-1, 0, -2]は[-1, -2, 0]になる必要がありますが、x > 0を使うと、コピー版は[0, 0, 0]を返します。- 0 がない配列や、0 だけの配列は、変更されずに返される必要があります。入れ替え版では、最初の 0 が現れるまで
readとwriteは等しいままなので、これらの入れ替えでは何も変わりません。 - Lua と R では配列のインデックスは 1 から始まるため、
writeも 1 から始めます。
よくある質問4
Move Zeroes の時間計算量は何ですか？
O(n)。どちらの方法も各要素を1回ずつ読み取ります。ゼロ以外の値を新しい配列にコピーするにはO(n)の追加メモリが必要ですが、2ポインターによる入れ替えはO(1)の追加メモリで配列内で処理できます。
ほかの要素の順序を変えずに、ゼロを末尾に移動するにはどうすればよいでしょうか？
先頭にある次の空き位置を示すwriteインデックスを保持し、2つ目のインデックスで走査します。見つけた0以外の値はそれぞれwriteの位置と入れ替え、writeを1つ右に進めます。値は見つけた順に配置されるため、相対的な順序は変わりません。
Move Zeroes は、書き込み回数を減らして実行できますか？
はい。入れ替える代わりに、0 でない値をそれぞれ nums[write] にコピーし、走査後に write から末尾までの各位置に 0 を入れます。これなら各位置への書き込みは最大 1 回です。また、read と write が等しい場合は、すでに値がある場所に値を戻すことになるため、入れ替えを省略できます。
なぜ Move Zeroes は2ポインター問題なのでしょうか？
一方のポインターはすべての要素を読み取り、もう一方は処理済みの先頭部分の末尾を示します。どちらも前方向にしか進まないため、合わせて1回の走査で済みます。同じ読み取りと書き込みのパターンで、ソート済み配列から重複を削除したり、配列内の任意の値をその場でフィルタリングしたりできます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def moveZeroes(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [0, 4, 0, 7, 2]
期待値
[4, 7, 2, 0, 0]