C++で配列内のすべてのゼロを末尾に移動する方法

複数のゼロ（0）を含む配列が与えられたとき、すべてのゼロを配列の末尾に移動させる必要があります。それ以外の要素は元の順序を保ったまま前に詰めます。具体例を見てみましょう。

入力

arr = [4, 5, 0, 3, 2, 0, 0, 0, 5, 0, 1]

出力

4 5 3 2 5 1 0 0 0 0 0

アルゴリズム

• 配列を初期化します。

• 書き込み位置を示すインデックス変数を 0 で初期化します。

• 与えられた配列を先頭から順に走査します。

  • 現在の要素がゼロでない場合、その値をインデックスの位置に書き込みます。

  • その後、インデックスを1つ進めます。

• 上記の処理が終わったインデックスから配列の長さ n まで繰り返すループを作成します。

  • 残りの要素をすべて 0 に更新します。

この手法では、ゼロ以外の要素だけを前側に詰めてから、余った後半部分をゼロで埋めるという流れになります。追加の配列を使わないため、空間計算量は O(1) で済みます。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
void moveZeroesToEnd(int arr[], int n) {
    int index = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {
            arr[index++] = arr[i];
        }
    }
    while (index < n) {
        arr[index++] = 0;
    }
}
int main() {
    int arr[] = {4, 5, 0, 3, 2, 0, 0, 0, 5, 0, 1};
    int n = 11;
    moveZeroesToEnd(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

4 5 3 2 5 1 0 0 0 0 0

計算量

• 時間計算量： 配列を一度だけ走査するため O(n) です。

• 空間計算量： 追加のメモリを使用しないため O(1) です。