C++で配列内の0を先頭へ、1を末尾へ移動する方法を解説

このチュートリアルでは、配列内のすべての0を先頭に移動し、すべての1を末尾に移動するプログラムをC++で作成する方法を解説します。

問題として、0と1がランダムな整数と混在した配列が与えられます。この配列に対して、すべての0を配列の先頭へ、すべての1を配列の末尾へ移動させる必要があります。まずは具体例を見てみましょう。

入力

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

出力

0 0 0 0 4 5 2 3 1 1 1 1

アルゴリズム

• 配列を初期化します。

• インデックス変数を0で初期化します。

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

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

  • 書き込んだ後にインデックスを1つ進めます。

• 走査終了後のインデックス位置から配列の末尾（n）までの残りの要素を、すべて1で埋めます。これにより、すべての1が配列の末尾に集まります。

• 次に、0についても同様の処理を行います。今度は配列を末尾から先頭方向へ走査し、インデックスを増やす代わりに減らしながら非ゼロ要素を詰めていくことで、すべての0を配列の先頭に移動させます。

実装

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

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

出力

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

0 0 0 0 4 5 2 3 1 1 1 1

このアルゴリズムは、配列を2回走査するだけで目的の並べ替えが完了するため、時間計算量はO(n)、追加のメモリを使用しないため空間計算量はO(1)という効率的なアプローチになっています。