JavaScriptで配列に存在しない最小の正の整数を見つける方法

JavaScriptでは、整数の配列を第一引数（唯一の引数）として受け取る関数を作成する必要があります。

この関数の役割は、配列に存在しない最小の正の整数を見つけて返すことです。

問題の例

たとえば、入力配列が次のような場合を考えてみましょう。

const arr = [4, 2, -1, 0, 3, 9, 1, -5];

このとき、期待される出力は次のとおりです。

const output = 5;

理由は簡単です。1、2、3、4はすでに配列内に存在していますが、5は配列に含まれていないため、存在しない最小の正の整数となります。

なお、負の数（-1、-5）や0は正の整数ではないため、答えの候補からは除外されます。

基本的なアプローチ

最も直感的な方法は、1から順番に数え上げていき、配列に含まれていない最初の値を見つけることです。Array.prototype.indexOf()メソッドを使えば、各候補の値が配列内に存在するかどうかを簡単に確認できます。

コード例

const arr = [4, 2, -1, 0, 3, 9, 1, -5];

const findSmallestMissing = (arr = []) => {
    let count = 1;

    // 配列が空またはnull / undefinedの場合は 1 を返す
    if (!arr?.length) {
        return count;
    };

    // count が配列に存在する限り、カウントを進める
    while (arr.indexOf(count) !== -1) {
        count++;
    };

    return count;
};

console.log(findSmallestMissing(arr));

出力結果

5

コードの解説

• 変数 count を 1 で初期化します（探索の開始点）。
• オプショナルチェイニング（?.）により、配列が空・null・undefined の場合でもエラーにならず、安全に 1 を返します。
• while ループ内で indexOf() を使い、count が配列に存在するかを判定します。存在すれば count をインクリメントして次の候補へ進みます。
• 配列に存在しない値に到達した時点でループを抜け、その値を結果として返します。

パフォーマンスを改善したSet版

上記の実装はシンプルで分かりやすい一方、indexOf() は呼び出しごとに線形時間 O(n) かかるため、最悪ケースの計算量は O(n²) になります。

データ量が多い場合は、Set を使うと効率的です。Set.has() は平均 O(1) で動作するため、全体の計算量を O(n) まで改善できます。

const findSmallestMissing = (arr = []) => {
    const set = new Set(arr);
    let count = 1;

    while (set.has(count)) {
        count++;
    };

    return count;
};

console.log(findSmallestMissing([4, 2, -1, 0, 3, 9, 1, -5])); // 5

まとめ

• 「存在しない最小の正の整数」は、1から順に確認していけば必ず見つかる。
• 小規模なデータなら indexOf() ベースの実装でも十分実用的。
• 大規模な配列を扱う場合は Set を活用することで、計算量を O(n²) から O(n) へ大幅に改善できる。