C++で配列の先頭にあるゼロ（先行ゼロ）を削除する方法

この記事では、与えられた配列から先頭のゼロ（先行ゼロ）を取り除き、その結果を出力する方法を解説します。

問題の概要

たとえば、次のような入力と出力を考えます。

入力 : arr[] = {0, 0, 0, 1, 2, 3}
出力 : 1 2 3

入力 : arr[] = {0, 0, 0, 1, 0, 2, 3}
出力 : 1 0 2 3

ご覧のとおり、配列の途中にあるゼロはそのまま残し、先頭に連続して並ぶゼロだけを削除するのがポイントです。

解決のアプローチ

基本的な方針はシンプルです。配列を先頭から走査し、最初の「ゼロではない要素」の位置を見つけることで、そこより前のゼロをすべて除外した新しい配列を作成します。

手順を整理すると以下のようになります。

1. 配列を左から順に調べ、最初の非ゼロ要素のインデックスを記録する
2. 非ゼロ要素が1つも存在しない場合は「Empty」などを出力して終了する
3. 見つかったインデックス以降の要素だけを新しい配列へコピーする
4. 新しい配列の内容を出力する

C++での実装例

#include <iostream>

using namespace std;

int main() {
    int arr[] = {0, 0, 0, 1, 2, 0, 4};
    int n = sizeof(arr) / sizeof(int); // 配列のサイズを求める
    int last = -1;
    for(int i = 0; i < n; i++) { // 最初の非ゼロ要素を探す
        if(arr[i] != 0) {
            last = i;
            break;
        }
    }
    if(last == -1)
        cout << "Empty\n";
    else {
        int b[n - last]; // 新しい配列
        for(int i = last; i < n; i++) // 新しい配列に要素を挿入
            b[i-last] = arr[i];

        for(int i = 0; i < n-last; i++) // 配列を出力
            cout << b[i] << " ";
    }
}

実行結果

1 2 0 4

コードの解説

このプログラムでは、まず配列 arr を先頭から走査し、最初の非ゼロ要素のインデックスを探して変数 last に格納しています。もし走査が終わっても last が -1 のままなら、配列全体がゼロで構成されていることを意味するため、「Empty」と出力します。

一方、最初の非ゼロ要素のインデックスが分かれば、新しい配列のサイズは (n - last) と計算できます。あとは last から n 未満まで for ループを回し、該当する要素を新しい配列 b にコピーして出力すれば、先頭のゼロが取り除かれた配列が得られます。

計算量について

このアルゴリズムは配列を最大2回走査するだけなので、時間計算量は O(n)、追加で必要なメモリも新しい配列分の O(n) となります。非常に効率的な方法です。

まとめ

この記事では、配列から先頭のゼロを削除する問題を取り上げました。最初の非ゼロ要素の位置さえ特定できれば、あとはその位置以降の要素をコピーするだけで簡単に実現できることが分かりました。同じロジックは C、Java、Python など他の言語でも同様に実装できます。ぜひ参考にしてみてください。