思路
看题第一眼想到的是先计算给定数组所有元素的乘积，然后对数组中的每个元素 $x$，将总的乘积除以 $x$ 来求得除自身值的以外数组的乘积。但当数组中出现$0$时，这个方法就失效了，且题目说明了不能使用除法。
不能使用除法，又怎么计算除自身值以外数组的乘积呢？考虑到 该数对应的乘积 =其左边的乘积 * 其右边的乘积。所以，可以通过两次遍历依次计算每个数的左右乘积即可得到答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums)
{
vector<int> ans;
// 计算每个数的左侧乘积
for(int i = 0; i < nums.size(); ++i)
{
if(i == 0)
{
ans.push_back(1);
}
else
{
ans.push_back(ans[i - 1] * nums[i - 1]);
}
}
// 计算每个数的右侧乘积, 并直接计算答案
for(int rc = 1, i = nums.size() - 1; i >= 0; --i)
{
if(i != (nums.size() - 1))
{
rc *= nums[i + 1];
}
ans[i] *= rc;
}
return ans;
}
};
|
zyz