构建乘积数组
构建乘积数组
http://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46
描述
这是一篇针对初学者的题解。
知识点:数组
难度:一星
题解
题目描述:给定一个长度为n的数组A,求数组B,B[i] = A[0]A[1]...A[i-1]*A[i+1]...A[n-1]。
要求不能使用除法。
方法:
根据题目描述,如果可以使用除法,就很简单。但是要求不能使用。
假设:left[i] = A[0]*...*A[i-1]
right[i] = A[i+1]*...*A[n-1]
所以:B[i] = left[i] * right[i]
这样就避免使用了除法。但是如果对每个B[i], 0<=i<n,都这么求,显然时间复杂度太高。
我们把整个结果画到下面图:
![图片说明](https://uploadfiles.nowcoder.com/images/20200506/284295_1588756073632_8F528B3C1F44C5BD5ED7012E809F9A49 "图片标题")
可知:left[i+1] = A[0]*...A[i-1]*A[i]
right[i+1] = A{i+2]*...*A[n-1]
于是,left[i+1] = left[i] * A[i]
right[i] = right[i+1] * A[i+1]
所以,我们可以先把所有的left[i]求出,right[i]求出。
代码如下:
class Solution { public: vector<int> multiply(const vector<int>& A) { vector<int> B(A.size(), 1); for (int i=1; i<A.size(); ++i) { B[i] = B[i-1] * A[i-1]; // left[i]用B[i]代替 } int tmp = 1; for (int j=A.size()-2; j>=0; --j) { tmp *= A[j+1]; // right[i]用tmp代替 B[j] *= tmp; } return B; } };
时间复杂度:O(N)
空间复杂度: O(1)