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 发布！