题目描述
给定一个数组
A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
数据范围
输入数组长度 [0,20]。
样例
输入：[1, 2, 3, 4, 5] 输出：[120, 60, 40, 30, 24]
思考题：
- 能不能只使用常数空间？（除了输出的数组之外）
方法一：空间复杂度为常数的算法 O(n)
由于题目限制不能使用除法，而且如果计算每个数都从前遍历一遍数组，时间复杂度就比较高。这里最优的做法就是动态的去更新数组信息，先计算每个数左边的乘积，再计算右边数的乘积。这样讲可能不那么直观，我们来看一个例子，假设给定数组 [1, 2, 3, 4, 5] 。
我们用一个容器 res 来存储答案，并且初始化 res[0] = 1 。
然后开始从左向右遍历数组，计算每个数左边数的乘积，并更新到 res 数组中。
最后再从右向左遍历数组，计算每个数右边的数的乘积，并将 res[i] 乘上右边数的乘积，就得到了除 A[i] 以外其它数的乘积。
class Solution { public: vector<int> multiply(const vector<int>& A) { if (A.empty()) return A; int n = A.size(); vector<int> res(n); res[0] = 1; //先计算每个数左边的乘积 for (int i = 1, p = A[0]; i < A.size(); i++) { res[i] = p; p *= A[i]; } //再计算每个数右边的乘积 for (int i = n - 2, p = A[n - 1]; i >= 0; i--) { res[i] *= p; p *= A[i]; } return res; } };
欢迎大家在评论区交流~
