題目
給你一個(gè)長度為 n 的整數(shù)數(shù)組 nums，其中 n > 1，返回輸出數(shù)組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。
示例
輸入: [1,2,3,4]
輸出: [24,12,8,6]
題目分析
實(shí)際上一個(gè)除自身以外數(shù)組的乘積就是一個(gè)數(shù)的左邊所有數(shù)和右邊所有數(shù)字的乘積非洲，因此，我們只要用兩個(gè)數(shù)組L和R分別儲(chǔ)存當(dāng)前坐標(biāo)左邊數(shù)字的乘積和右邊數(shù)字的乘積蜕径，最后按照坐標(biāo)依次相乘即可两踏。
首先初始化兩個(gè)數(shù)組：
int len = nums.size();
vector<int> L(len, 1);
vector<int> R(len, 1);
for (int i = 1; i < len; i++) {
L[i] = L[i - 1] * nums[i - 1];
}
for (int i = len - 2; i >= 0; i--) {
R[i] = R[i + 1] * nums[i + 1];
}
然后得到最后的結(jié)果：
vector<int> res;
for (int i = 0; i < len; i++){
res.push_back(L[i] * R[i]);
}
return res;
但是通過上述的過程我們可以明顯發(fā)現(xiàn)，在計(jì)算并儲(chǔ)存了左乘積以后兜喻，再次儲(chǔ)存右乘積對(duì)空間明顯浪費(fèi)梦染，所以我們可以優(yōu)化空間復(fù)雜度，全程只使用一個(gè)數(shù)組朴皆，儲(chǔ)存左乘積帕识，并在此數(shù)字的基礎(chǔ)上運(yùn)算最后結(jié)果返回。
int R = 1;
for (int i = len - 2; i >= 0; i--) {
R *= nums[i + 1];
res[i] *= R;
}
return res;
題目解答
常數(shù)級(jí)空間復(fù)雜度
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
int* res = (int*)calloc(numsSize, sizeof(int));
res[0] = 1;
for (int i = 1; i < numsSize; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
// 然后計(jì)算右邊
int R = 1;
for (int i = numsSize - 2; i >= 0; i--) {
R *= nums[i + 1];
res[i] *= R;
}
return res;
}
