【ITニュース解説】🎯 Master the Move Zeros Algorithm:

このニュース記事では、「Move Zeros」と呼ばれる配列の操作アルゴリズムについて解説している。これは、与えられた配列の中にあるすべてのゼロを配列の末尾に移動させ、同時にゼロ以外の要素の相対的な順序を保つという課題である。例えば、[0, 1, 0, 3, 12] という配列が与えられた場合、最終的には [1, 3, 12, 0, 0] という形にする。

この課題にはいくつかの重要な制約がある。一つ目は、ゼロ以外の要素（この例では1, 3, 12）は、元の配列での並び順（1→3→12）を維持しなければならないことだ。二つ目は、「インプレース」で処理を行う必要があることだ。これは、新しい配列を別に作成することなく、元の配列を直接変更して結果を得ることを意味する。追加で使用するメモリは非常に少なく、専門用語で「O(1)空間計算量」と呼ばれる状態を目標とする。三つ目は、配列を効率的に処理するために、「シングルパス」、つまり配列を最初から最後まで一度だけ見て処理を完了することが望ましい。これは専門用語で「O(n)時間計算量」と呼ばれ、配列の要素数に比例する時間で処理が完了することを示す。

この問題を解決するために、「2つのポインタ」というテクニックが使われる。これは、配列の異なる位置を指す二つの変数（ポインタ）を同時に動かすことで、効率的な処理を実現する方法である。具体的なJavaコードを見ると、left と right という二つの整数型変数がポインタとして宣言されている。

left ポインタは、次に非ゼロの要素を配置すべき位置を示す。初期値は配列の先頭である0に設定される。一方、right ポインタは、配列全体を最初から最後まで探索し、現在見ている要素の位置を示す。right ポインタは、配列の先頭から終端まで一つずつ進んでいく。

アルゴリズムの基本的な考え方はこうだ。right ポインタが配列を走査しているとき、もし nums[right] で示される要素がゼロでない場合、その非ゼロ要素を nums[left] の位置に移動させる。そして、非ゼロ要素を配置した left ポインタを一つ進めて、次に非ゼロを置くべき新しい場所を示す。もし nums[right] がゼロである場合、そのゼロは一時的に無視され、left ポインタは動かず、right ポインタだけが一つ進む。これにより、left ポインタより前の位置には非ゼロ要素だけが集まり、ゼロは自然と配列の末尾に追いやられることになる。

具体的な例でアルゴリズムの動作を追ってみよう。初期配列が [0, 1, 0, 3, 12] で、left = 0 から始まる。

1. right = 0 のとき、nums[0] は 0 である。ゼロなので、何もしない。配列は [0, 1, 0, 3, 12] のままで、left は 0 のままだ。
2. right = 1 のとき、nums[1] は 1 である。これはゼロではないので、スワップ（入れ替え）が必要になる。nums[left] (つまり nums[0]) の 0 と nums[right] (つまり nums[1]) の 1 を入れ替える。配列は [1, 0, 0, 3, 12] となる。スワップが完了したら、left を一つ進めて 1 にする。
3. right = 2 のとき、nums[2] は 0 である。ゼロなので、何もしない。配列は [1, 0, 0, 3, 12] のままで、left は 1 のままだ。
4. right = 3 のとき、nums[3] は 3 である。これはゼロではないので、スワップが必要になる。nums[left] (つまり nums[1]) の 0 と nums[right] (つまり nums[3]) の 3 を入れ替える。配列は [1, 3, 0, 0, 12] となる。スワップが完了したら、left を一つ進めて 2 にする。
5. right = 4 のとき、nums[4] は 12 である。これはゼロではないので、スワップが必要になる。nums[left] (つまり nums[2]) の 0 と nums[right] (つまり nums[4]) の 12 を入れ替える。配列は [1, 3, 12, 0, 0] となる。スワップが完了したら、left を一つ進めて 3 にする。

right ポインタが配列の最後まで到達したため、処理は終了する。最終結果は [1, 3, 12, 0, 0] となり、非ゼロ要素の順序が保たれつつ、ゼロが末尾に移動していることがわかる。

このアルゴリズムの背後にある重要な考え方は「不変条件」と呼ばれるものだ。これは、アルゴリズムの実行中、常に特定の状態が保たれていることを意味する。この場合、「left ポインタよりも前にあるすべての要素は、元の相対的な順序で非ゼロ要素のみを含んでいる」という条件が常に満たされている。left ポインタは非ゼロ要素を配置したときにだけ進むため、この条件が自動的に維持されるのだ。これにより、最終的に left ポインタが指す位置から後方にはゼロが残されることになる。

開発者がよく陥る間違いの一つに、left ポインタのインクリメント（値を一つ増やすこと）を誤った場所に記述してしまうことがある。もし left++ を if (nums[right] != 0) という条件式の外に置いてしまうと、right ポインタがゼロを見つけた場合でも left ポインタが進んでしまう。これでは、left ポインタが次に非ゼロ要素を置くべき正しい位置を見失ってしまい、アルゴリズムは正しく機能しない。left ポインタは、非ゼロ要素を見つけてスワップが完了したときにだけ進める、というルールを厳守することが非常に重要である。

スワップ（要素の入れ替え）には二つのケースがある。一つは left と right が同じ位置を指している場合だ。この場合、nums[left] と nums[right] を入れ替えても、同じ要素同士の入れ替えなので配列には見た目の変化はない。もう一つは left が right より小さい場合だ。このとき、nums[left] は通常、すでに処理された非ゼロ要素の直後の位置（つまりゼロである可能性が高い位置）を指し、nums[right] は現在 right が見つけた非ゼロ要素を指す。このスワップによって、非ゼロ要素はより前方に移動し、ゼロはより後方に移動することになる。

このアルゴリズムは、非常に効率的であると評価できる。

• 時間計算量: O(n)である。right ポインタが配列を一度だけ走査するため、配列の要素数 n に比例する時間で処理が完了する。各要素に対して行われる処理は定数時間（常に同じ短い時間）で終わるため、非常に効率が良い。
• 空間計算量: O(1)である。left と right という二つのポインタ変数しか追加のメモリを使用しないため、配列のサイズがどれだけ大きくても、必要な追加メモリの量は一定である。
• 安定性: このアルゴリズムは安定であると言える。なぜなら、ゼロ以外の要素の相対的な順序が維持されるためだ。
• インプレース: 元の配列を直接変更して結果を得るため、この要件も満たしている。

この「2つのポインタによるパーティショニング」というアルゴリズムパターンは、様々な問題に応用できる。例えば、負の数を配列の左側に移動させたり、偶数と奇数を分離したり、あるいは「ダッチ・ナショナル・フラッグ問題」のように複数の種類の要素をソートしたりする際に利用できる。left ポインタが「適切に処理されたセクション」を維持し、right ポインタが「探索セクション」を進めるという考え方が共通している。

このアルゴリズムを理解することで、2つのポインタが複雑な配列の並べ替え問題を効率的に解決できること、アルゴリズムの正しさを理解するには不変条件が重要であること、そしてポインタのインクリメントなど操作の配置がいかに重要であるかという、プログラミングにおける重要な教訓を得られる。また、一度学んだパターンが他の類似問題の解決にも役立つという「パターン認識」の重要性も理解できる。