自身を除く配列の積 - tanakakenji/Rinko GitHub Wiki

問題: 自身を除く配列の積

問題文

整数の配列 nums が与えられたとき、answer[i] が nums[i] を除く nums のすべての要素の積となるような配列 answer を返してください。

制約:

  • アルゴリズムは O(n) の時間複雑度で動作する必要があります。
  • 除算の使用は禁止されています。

例: 入力: nums = [1,2,3,4] 出力: [24,12,8,6]

解答 (C++)

#include <vector>
#include <iostream>

class Solution {
public:
    std::vector<int> productExceptSelf(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> answer(n, 1);
        
        // 左からの積を計算
        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            answer[i] *= leftProduct;
            leftProduct *= nums[i];
        }
        
        // 右からの積を計算しながら、最終的な結果を得る
        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        
        return answer;
    }
};

// テスト用のメイン関数
int main() {
    Solution sol;
    std::vector<int> nums = {1, 2, 3, 4};
    auto result = sol.productExceptSelf(nums);
    
    // 結果の出力
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

解説

  1. 事前計算の重要性:

    • この問題は、事前計算のテクニックを活用することで効率的に解決できます。
    • 各要素について、その左側の全要素の積と右側の全要素の積を別々に計算することで、除算を使わずに解を得ることができます。

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

    • まず、配列を左から右に走査し、各位置での左側の要素の積を計算します。
    • 次に、配列を右から左に走査し、各位置での右側の要素の積を計算しながら、最終的な結果を得ます。

  3. 時間複雑度:

    • 配列を2回走査するだけなので、時間複雑度は O(n) です。
    • これは問題の制約を満たしています。

  4. 空間複雑度:

    • 結果を格納する配列以外の追加の空間を使用していないので、空間複雑度は O(1) です（出力配列は空間複雑度に含めないという一般的な規則に従います）。

  5. 除算を使用しない理由:

    • 除算を使用すると、配列内に0が存在する場合に問題が発生します。
    • また、浮動小数点数の精度の問題を避けることができます。

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

    • std::vectorを使用して動的配列を扱っています。
    • 範囲ベースのfor文を使用して、結果の出力を行っています。

  7. 最適化のポイント:

    • 一時的な配列を使用せずに、結果の配列を直接操作することで、メモリ使用量を最小限に抑えています。
    • 2回のループを1つの関数内で行うことで、コードの簡潔さを保っています。

  8. 面接での注意点:

    • この解法が O(n) の時間複雑度を持つことを説明できることが重要です。
    • なぜ除算を使用しない解法が必要かを理解し、説明できることも重要です。
    • 事前計算のアイデアをどのように思いついたか、その思考プロセスを説明できると良いでしょう。

この問題は、事前計算のテクニックが如何に効果的かを示す良い例です。単純に各要素について他の全ての要素の積を計算すると O(n^2) の時間複雑度になりますが、事前計算を用いることで O(n) に改善できます。これは、効率的なアルゴリズム設計における事前計算の重要性を示しています。

⚠️ **GitHub.com Fallback** ⚠️