Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
这道题讲道理第一遍写的时候没考虑到有数组中有出现0的情况,后面又仔细一看不能用除法,这里犯的另一个错误是vector的初始化问题。leetcode中文版中有详细的解释。
解法一:
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int elem_size = nums.size();
vector<int> res(elem_size);
vector<int> left(elem_size);
left[0]=1;
vector<int> right(elem_size);
right[0]=1;
for(int i = 1;i < elem_size;i++)
{
left[i] = nums[i - 1]*left[i-1];
right[i] = nums[elem_size - i] * right[i -1];
}
for(int i = 0;i < elem_size;i++)
{
res[i] = left[i] * right[elem_size - 1 -i];
}
return res;
}
};
解法二:
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int N = nums.size();
vector<int> res(N,1);
for(int i = 1;i < N;i++)
{
res[i] = res[i - 1] * nums[i - 1];
}
int right_start = 1;
for(int i = N - 1;i >= 0;i--)
{
res[i] = res[i] * right_start;
right_start = right_start * nums[i];
}
return res;
}
};
一种可能的出错:
Runtime Error
Line 924: Char 9: runtime error: reference binding to null pointer of type 'int' (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_vector.h:933:9
这种有可能是将方法一种的如下代码写成了错误形式:
//正确形式:
int elem_size = nums.size();
vector<int> res(elem_size);
vector<int> left(elem_size);
//错误形式:
int elem_size = nums.size();
vector<int> res;
vector<int> left;