⓺➁ Product of Array Except Self

Top Interview 150, leetcode medium, C++, Algorithm

Today’s code

Idea

這裡直覺的解法是將原本的vector，分成兩個部分，而中間是用什麼區隔呢？就是用我們要return的vector之index區隔成左半部與右半部。

以下的寫法與思路是分別去假設我們的目標index，模擬法的方式去計算出所有除了自己之外的元素乘積（product）。

但這樣的寫法時間複雜度會是O(N ^ 2)，因為是雙層迴圈。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
      // 創建新的vector 用於儲存答案
        vector<int> ans_nums;
        for(int target_index = 0; target_index < length; target_index++){
            int tmp_product = 1;
            
      // 計算乘積範圍由最左邊到我們的目標index
            for(int left_index = 0; left_index < target_index; left_index++){
                tmp_product *= nums[left_index];
            }
    // 從目標index的下一位開始，到整個陣列的最後
            for(int right_index = target_index + 1; right_index < length; right_index++){
                tmp_product *= nums[right_index];
            }
      // push_back 此API用於加入新元素在vector
            ans_nums.push_back(tmp_product);
        }
        return ans_nums;
    }
};

Idea 2 製作表格清單？！

我們從上面第一個寫法，可以聯想到幾件事，乘積和可以透過前面的元素去計算。換句話說，我們可以分別去紀錄不同的目標index的左右部分的乘積和。

這樣的設計方式，我們的時間複雜度變為O(N)，再次囉唆一次提醒。left_product所儲存的元素是左側的乘積和，但是是以哪一個為標準呢？

是根據index為標準，有就是說我們的ans_nums這個vector中的index = 0時，其左側成績和為1，對應到left_product[0] = 1，也是正確。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> left_product(length);
        vector<int> right_product(length);
        vector<int> ans_nums(length);
        left_product[0] = 1;
        for(int i = 1; i < length; i++){
            left_product[i] = left_product[i - 1] * nums[i - 1];
        }

        right_product[length - 1] = 1;
        for(int i = length - 2; i > -1; i--){
            right_product[i] = right_product[i + 1] * nums[i + 1];
        }

        // calculate ans
        for(int i = 0; i < length; i++){
            ans_nums[i] = left_product[i] * right_product[i];
        }

        return ans_nums;
    }
};

Idea 2 進階挑戰 /只創建一個vector去儲存

其實就是將上面的寫法做精簡，我們可以發先這個版本的vector只會有一個，ans_nums用於去計算出要return的結果，等於是說我們將ans_nums作為“暫時的”left_product，再去累計乘積，計算出答案。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> ans_nums(length);
        ans_nums[0] = 1;
        for(int i = 1; i < length; i++){
            ans_nums[i] = ans_nums[i - 1] * nums[i - 1];
        }

        int right = 1;
        
        for(int j = length - 2; j > -1; j--){
            ans_nums[j] *= right * nums[j + 1];
            right *= nums[j + 1]; 
        }
        return ans_nums;
    }
};

https://leetcode.com/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-interview-150