整数の配列 nums が与えられたとき、その配列に存在しない最小の正の整数を見つけてください。

アルゴリズムは O(n) の時間複雑度で動作し、O(1) の追加空間しか使用しないようにしてください。

例: 入力: nums = [3,4,-1,1] 出力: 2 説明: 1は配列に存在しますが、2は存在しないため、2が答えとなります。

#include <vector>
#include <iostream>

class Solution {
public:
    int firstMissingPositive(std::vector<int>& nums) {
        int n = nums.size();
        
        // Step 1: 1からnの範囲外の数を1に置き換える
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = 1;
            }
        }
        
        // Step 2: 存在する数のインデックスを負にマークする
        for (int i = 0; i < n; i++) {
            int index = std::abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        // Step 3: 最初の正の数のインデックス + 1 が答え
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        
        // Step 4: すべての数が存在する場合、n + 1 が答え
        return n + 1;
    }
};

// テスト用のメイン関数
int main() {
    Solution sol;
    std::vector<int> nums = {3, 4, -1, 1};
    int result = sol.firstMissingPositive(nums);
    
    std::cout << "The first missing positive integer is: " << result << std::endl;
    
    return 0;
}

1. インデックスをハッシュキーとして使用する重要性:

   • この問題では、配列自体をハッシュテーブルとして使用することで、O(1)の追加空間という厳しい制約を満たしています。
   • 各数値の存在を、そのインデックスに対応する要素の符号で表現することがキーポイントです。

2. アルゴリズムの流れ:

   • Step 1: 1からnの範囲外の数を1に置き換えます。これにより、すべての要素が有効なインデックスを指すようになります。
   • Step 2: 各数値の存在を、そのインデックスの要素を負にすることでマークします。
   • Step 3: 最初の正の数のインデックス + 1が、欠落している最小の正の整数となります。
   • Step 4: すべての数が存在する場合、n + 1が答えとなります。

3. 時間複雑度:

   • 配列を3回走査するだけなので、時間複雑度は O(n) です。

4. 空間複雑度:

   • 入力配列自体をハッシュテーブルとして使用しているため、追加の空間は O(1) です。

5. インデックスをハッシュキーとして使用するテクニック:

   • 配列のインデックスを1からnまでの数値と対応させることで、追加のハッシュテーブルなしで各数値の存在を記録できます。
   • 要素の符号を変更することで情報を記録するのは、このテクニックの典型的な使用方法です。

6. C++での実装の特徴:

   • std::abs() 関数を使用して、マーキングの際に絶対値を取得しています。
   • vector の size() メソッドを使用して配列の長さを取得しています。

7. 注意点:

   • このアルゴリズムは入力配列を変更します。これが許容されない場合は、別のアプローチが必要になります。
   • 0や負の数を1に置き換えることで、これらの数値に関する情報は失われますが、問題の制約上これは問題ありません。

8. 面接での注意点:

   • このアルゴリズムがO(n)の時間複雑度とO(1)の空間複雑度を持つことを説明できることが重要です。
   • なぜ配列自体をハッシュテーブルとして使用できるのか、その考え方を説明できると良いでしょう。
   • エッジケース（空の配列、すべての正の整数が存在する場合など）についても考慮していることを示すと、より深い理解を示すことができます。

この問題は、配列自体をハッシュテーブルとして使用するテクニックの典型的な例です。このテクニックを使用することで、追加の空間を使用せずに効率的にデータを処理することができます。これは、空間効率が重要視される問題や、メモリ制約の厳しい環境での最適化に非常に有用です。

はい、具体的な数字を使って、このアルゴリズムの各ステップを詳しく解説いたします。サンプル入力 {3, 4, -1, 1} を使用して説明します。

1. 初期状態:

   nums = [3, 4, -1, 1]
   n = 4
   

2. Step 1: 1からnの範囲外の数を1に置き換える

   for (int i = 0; i < n; i++) {
       if (nums[i] <= 0 || nums[i] > n) {
           nums[i] = 1;
       }
   }
   

   実行後:

   nums = [3, 4, 1, 1]
   

   -1 が 1 に置き換えられました。

3. Step 2: 存在する数のインデックスを負にマークする

   for (int i = 0; i < n; i++) {
       int index = std::abs(nums[i]) - 1;
       if (nums[index] > 0) {
           nums[index] = -nums[index];
       }
   }
   

   実行過程:

   • i = 0: nums[0] = 3, index = 2, nums[2] becomes -1

     nums = [3, 4, -1, 1]
     

   • i = 1: nums[1] = 4, index = 3, nums[3] becomes -1

     nums = [3, 4, -1, -1]
     

   • i = 2: nums[2] = -1, index = 0, nums[0] becomes -3

     nums = [-3, 4, -1, -1]
     

   • i = 3: nums[3] = -1, index = 0, nums[0] は既に負なので変更なし

4. Step 3: 最初の正の数のインデックス + 1 が答え

   for (int i = 0; i < n; i++) {
       if (nums[i] > 0) {
           return i + 1;
       }
   }
   

   実行結果:

   nums = [-3, 4, -1, -1]
   

   インデックス 1 の数が正なので、1 + 1 = 2 が返されます。

5. Step 4: この場合は実行されません。

最終的に、関数は 2 を返します。これは、配列 {3, 4, -1, 1} において最小の欠落している正の整数が 2 であることを意味します。

このアルゴリズムは、配列自体をハッシュテーブルとして使用し、各数の存在を負の符号でマークすることで、追加の空間を使用せずに問題を解決しています。これにより、O(n) の時間複雑度と O(1) の空間複雑度を実現しています。