题目

找到数组中每个元素除了自己以外的乘积,比如输入:[1,2,3,4],输出[2*3*4,1*3*4,1*2*4,1*2*3]即[24, 12, 8, 6]

方法一

可以看到每个元素的值相当于左边部分的乘积再乘以右边部分的乘积,
比如:

1
2
3
4
5
输入: [1,2,3,4]
第一个元素相当于 () * (2*3*4)
第二个元素相当于 (1) * (3*4)
第三个元素相当于 (1*2) * (4)
第四个元素相当于 (1*2*3) * ()

维持两个数组,一个是从左到右的累乘,一个是从右到左的累乘。
比如:

1
2
3
4
输入: [1,2,3,4]
从左到右的累乘lToR:[1,2,6,24]
从右到左的累乘rToL:[24,24,12,4]
则每个元素的值相当于lToR[i-1] * rToL[i+1]

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
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int all = 1;
vector<int> lToR;
vector<int> rToL;
vector<int> result;
for (int num: nums) {
all *= num;
lToR.push_back(all);
}
all = 1;
for (auto it = nums.rbegin(); it != nums.rend(); it++) {
all *= *it;
rToL.push_back(all);
}
reverse(rToL.begin(), rToL.end());
for (int i = 0; i < nums.size(); i++) {
int left = 1, right = 1;
if (i>0) left = lToR[i-1];
if (i+1<nums.size()) right = rToL[i+1];
result.push_back(left * right);
}
return result;
}
};

需要空间复杂度O(n),时间复杂度O(n)

方法二

方法一需要额外的空间来存储两个不同方向的累乘,方法二将rToL存放到result中,lToR里面的值可以随着循环乘以nums中元素来获得,就不需要额外的空间来存放它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int all = 1;
vector<int> result;
for (auto it = nums.rbegin(); it != nums.rend(); it++) {
all *= *it;
result.push_back(all);
}
reverse(result.begin(), result.end());
int product = 1;
for (int i = 0; i < nums.size(); i++) {
int left = 1, right = 1;
if (i>0) left = product;
if (i+1<nums.size()) right = result[i+1];
result[i] = left * right;
product *= nums[i];
}
return result;
}
};

需要空间复杂度O(1),时间复杂度O(n)