IT工程師數位筆記本

題目描述
給定一個數組A[0,1,...,n-1],請構建一個數組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

這題不準用除法，那么就轉化。首先想到的是用“先取log再e回去”的做法，但是因為坑比較多，比如A[i]等于0的情況，log處理0不好弄。

但是這種思路并非一無是處。當發現log 0做不下去，就容易想到直接元素A[i]左右兩側各個元素的乘積left和right，它倆的乘積left x right就是最終的結果啊。

那么結果數組的每個元素B[i]就分解成左右兩部分的乘積。代碼就是網上找到的通用版本那個了。復雜度O(n^2)

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size());
        
        vector<int> left(A.size());
        left[0] = 1;

        cout << "left:" << endl;
        for (int i = 1; i<A.size(); i++){
            left[i] = left[i - 1] * A[i-1];
        }
        for (int i = 0; i < A.size(); i++){
            cout << left[i] << " ";
        }
        cout << endl;

        cout << "right:" << endl;
        vector<int> right(A.size());
        right[A.size()-1] = 1;
        for (int i = A.size()-2; i>=0; i--){
            right[i] = right[i + 1] * A[i+1];
            //cout << right[i] << " ";
        }
        for (int i = 0; i < A.size(); i++){
            cout << right[i] << " ";
        }
        cout << endl;

        for (int i = 0; i<B.size(); i++){
            B[i] = left[i] * right[i];
        }
        return B;
    }
};