Description:
https://leetcode.com/problems/product-of-array-except-self/#/description
Algorithm:
As shown in Code.
Code1 (62ms, beats 20.95%):
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> fromLeft = vector<int>(n, 1);
vector<int> fromRight = vector<int>(n, 1);
vector<int> result = vector<int>(n, 1);
for (int i = 1; i < nums.size();i++)
{
fromLeft[i] = nums[i – 1] * fromLeft[i – 1];
}
for (int i = nums.size() – 2; i >= 0;i–)
{
fromRight[i] = nums[i + 1] * fromRight[i + 1];
}
for (int i = 0; i < nums.size();i++)
{
result[i] = fromLeft[i] * fromRight[i];
}
return result;
}
};
Code2 (46ms, fastest):
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res;
res.push_back(1);
for(int i = 1; i<nums.size(); i++){
int temp = res[i-1]*nums[i-1];
res.push_back(temp);
}
int right = 1;
for(int i = nums.size()-1; i>=0; i–){
res[i] *= right;
right *= nums[i];
}
return res;
}
};