题目:
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).
For example, given [1,2,3,4]
, return [24,12,8,6]
.
代码:
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> fromBegin(n);
vector<int> fromLast(n);
fromBegin[] = fromLast[] = ;
for(int i = ; i < n; ++i)
{
fromBegin[i] = fromBegin[i-] * nums[i-];
fromLast[i] = fromLast[i-] *nums[n-i];
}
vector<int> res(n);
for(int i = ; i < n; ++i)
{
res[i] = fromBegin[i]*fromLast[n-i-];
}
return res;
}
};