🔍 First Missing Positive アルゴリズム解析

問題：ソートされていない整数配列から、存在しない最小の正の整数を見つける
制約：O(n)時間、O(1)空間で実装する

📊 デモンストレーション

🔧 アルゴリズムの詳細解説

Step 1: 値の正規化 (Normalization)

                    for (let i = 0; i < n; i++) { if (nums[i] <= 0 || nums[i] > n) { nums[i] = n +
                    1; // 範囲外の値を統一 } }
                

目的：1からnの範囲外の値（0以下、n+1以上）をn+1に統一
理由：最小の欠けている正の整数は必ず1〜(n+1)の範囲にあるため、範囲外の値は無視できる

Step 2: 存在マーキング (Marking)

                    for (let i = 0; i < n; i++) { const val = Math.abs(nums[i]); if (val <= n) {
                    nums[val - 1] = -Math.abs(nums[val - 1]); } }
                

目的：各数値の存在を配列の符号で記録
仕組み：値xが存在する場合、インデックス(x-1)の値を負にマーク
ポイント：絶対値を使うことで元の値を保持しながらマーキング

Step 3: 結果の検出 (Detection)

                    for (let i = 0; i < n; i++) { if (nums[i] > 0) { return i + 1; //
                    最初の正の値のインデックス+1 } } return n + 1; // 全て存在する場合
                

目的：最初の正の値を見つけて答えを返す
論理：インデックスiが正 → 値(i+1)が存在しない → 答えは(i+1)
特殊ケース：全て負の場合は1〜nが全て存在するため答えは(n+1)

⚡ 計算量解析

⏱️ 時間複雑度: O(n)

💾 空間複雑度: O(1)

時間複雑度の内訳：
• Step 1: O(n) - 全要素を1回スキャン
• Step 2: O(n) - 全要素を1回スキャン
• Step 3: O(n) - 最悪の場合全要素をスキャン
合計: O(n) + O(n) + O(n) = O(n)

空間複雑度の説明：
入力配列以外に追加のデータ構造を使用せず、定数個の変数のみ使用するためO(1)

🎯 アルゴリズムの核心アイデア

🔑 Key Insight: 配列自体をハッシュテーブルとして活用

問題：O(1)空間制約でどうやって存在チェックを行う？
解決策：配列のインデックスと値の対応関係を利用
マッピング：値x → インデックス(x-1)の符号でマーク
利点：追加メモリ不要、O(1)でアクセス可能