題目描述
原題鏈接：Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6]
給定一個(gè)長(zhǎng)度大于1的數(shù)組彩郊，計(jì)算出一組乘積output[n]，output[i]等于這個(gè)數(shù)組里除去nums[i]的所有數(shù)的積蚪缀。要求時(shí)間復(fù)雜度在O(n)內(nèi)且不含除法秫逝。
思路
這一題乍一看很簡(jiǎn)單，計(jì)算出所有數(shù)的積然后分別除掉每個(gè)數(shù)就行了询枚，但原題要求不能用除法违帆。那么，我們就只能使用乘法了哩盲。在只使用乘法的情況下想要時(shí)間復(fù)雜度達(dá)到O(n)前方，則需要避免其中重復(fù)計(jì)算。
假設(shè)對(duì)于數(shù)組 nums[]={2, 3, 4, 5 }, 假設(shè)result[]為最后結(jié)果廉油，可以得到：
result.jpg
只需要計(jì)算出A惠险、B這兩個(gè)三角形上每行的乘積，就可以得到result了抒线。比如：
A[0]=1,A[1]=2,A[2]=2*3=6,A[3]=2*3*4=24;
B[0]=3*4*5=60,B[1]=4*5=20,B[2]=5,B[3]=1;
result[0]=A[0]*B[0],result[1]=A[1]*B[1];
以此類推班巩。
計(jì)算A、B就簡(jiǎn)單了嘶炭，完全可以在O(n)內(nèi)辦到抱慌。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> result;
vector<int> leftSum ;
vector<int> rightSum ;
if (nums.size()<2)
return result;
int leftTemp=1;
int rightTemp=1;
leftSum.push_back(leftTemp);
rightSum.push_back(rightTemp);
for (int i=0;i+1<nums.size();i++){
leftTemp *= nums[i];
leftSum.push_back(leftTemp);
}
for (int i=nums.size()-1;i>=1;i--){
rightTemp*=nums[i];
rightSum.push_back(rightTemp);
}
reverse(rightSum.begin(),rightSum.end());
for (int i=0;i<leftSum.size();i++){
result.push_back(leftSum[i]*rightSum[i]);
}
return result;
}
};