剑指offer 66. 构建乘积数组
题目：
给定一个数组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]。不能使用除法。
同leetcode 238
https://leetcode.com/problems/product-of-array-except-self/
分析：
假如可以利用除法，则利用(A[0]*A[1]*...A[n-1])/A[i]，但一定要注意A[i]等于 0 的情况！！！
暴力解决需要使用O(n^2)来构建数组B，不够高效。
使用O(n)的时间复杂度来解决本题：
思路比较巧妙，我们知道B[i] = A[0] * A[1] * ... * A[i-1] * A[i+1] ... A[n-1]，所以我们将B[i]得到的过程分为两部分：
第一部分：A[0] * A[1] * ... * A[i-1]；第二部分： A[i+1] * ... * A[n-1]
我们先“自底向上”计算第一部分，并存储到B中；然后“自顶向下”计算第二部分，并结合B中的第一部分，“自顶向下”更新B中元素。
两个顺序的for循环解决问题。
void multiply(const vector<double>& array1, vector<double>& array2) {
int length1 = array1.size();
int length2 = array2.size();
if (length1 == length2 && length2 > ) {
array2[] = ;
// 计算并存储第一部分
for (int i = ; i < length1; ++i) {
array2[i] = array2[i - ] * array1[i - ];
}
// 计算第二部分并更新array2
double temp = ;
for (int i = length1 - ; i >= ; --i) { // 此时array2[length2 -1]已为正确值
temp *= array1[i + ];
array2[i] *= temp;
}
}
}
总结：
本解决方法时间复杂度为O(n)。
本题解决思路巧妙，也是对于问题观察得来的结果。也许想到分成两部分来说不难，尤其是做过一遍之后，但是两个for循环的写法非常值得借鉴，也是对整个清晰思路的完美反映。