LeetCode刷題記錄——day2

https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150
問題在於不使用除法並且空間複雜度為O(1)，當第一次從頭開始遍歷時由於不知道後續數組元素是什麼，所以無法得到答案，而如果當知道一個後續數組元素後，又回去更新答案的話，無疑會提高時間複雜度。不妨這樣看待，如果我們已經遍歷一次數組並且能夠記錄下足夠的信息的話，那麼下次我們再次遍曆數組時不就可以相對地知道後續元素的信息了嗎。由此推廣，為了演算法簡單一些，我們甚至可以遍歷有限次，獲得足夠的信息，然後一次得到最終答案。
由這樣的思路我們再看問題，對於任何一個元素，其除了自身以外的的元素的乘積由兩個部分構成，一個是它的前序元素乘積，一個是後續元素乘積。前者可以通過正向的遍歷得到，後者通過反向遍歷也可以得到，由此答案就明瞭了；

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int len = nums.size();
        vector<int> answer(len);
        int answer_R[len],answer_L[len];
        answer_L[0]=1,answer_R[len-1]=1;
        for(int i=1;i<len;i++){
            answer_L[i]=answer_L[i-1]*nums[i-1];
        }
        for(int i=len-2;i>=0;i--){
            answer_R[i]=answer_R[i+1]*nums[i+1];
        }
        for(int i=0;i<len;i++){
            answer[i]=answer_L[i]*answer_R[i];
        }
        return answer;
    }
};

同理，其實我們不需要兩個數組，只需要一個中間變數記錄後續乘積的過程就可以了，這樣可以減小空間複雜度；

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

本文由博客一文多發平臺 OpenWrite 發佈！