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 of nums except nums[i].
Solve it without division and in O(n).
题目的大意是:给定一个数组,包含n个数(n大于1),返回一个数组,这个数组里面的第i个元素是原来数组中除第i个数之外的所有数的乘积。 不使用除法解决这个问题
For example, given [1,2,3,4], return [24,12,8,6].
附加要求: Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
使用常量的内存空间(输出数组除外)
其实我这个解法是错误的,因为一开始没有看到题目中的一句话“Solve it without division”。但是我写都已经写了,哎,凑合吧。 我的解法是用不变量的方法,所有的数的乘积是一个不变量,每次除以当前的元素的商即是第i个结果,如果第i个数是零,那就重新计算其他数的乘积。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int totalSum=1,resulti,totalSum2=1;
vector<int> result;
int length=nums.size();
//count total
for(int i=0;i//calculate each
for(int i=0;iif(nums[i]!=0){
result.push_back(totalSum/nums[i]);
}else{//nums[i]==0
for(int j=0;jif(j==i)
continue;
totalSum2*=nums[j];
}
result.push_back(totalSum2);
}
}
return result;
}
};
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int left = 1, right = 1, n = nums.size();
vector<int> res(n, 1);
for (int i = 0; i < n; i++) {
res[i] *= left;
left *= nums[i]; // i's left part
res[n - i - 1] *= right;
right *= nums[n - i - 1]; // i's right part
}
return res;
}
};