[剑指offer] 51. 构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

---

思路：

当作一个上三角和下三角，分别用两个for去乘上三角和下三角。

class Solution { public: vector<int> multiply(const vector<int> &A) { vector<int> B; if (A.empty()) return B; int len = A.size(); B.push_back(1); for (int i = 1; i < len; i++) { B.push_back(B[i - 1] * A[i - 1]); } int temp = 1; for (int i = len - 2; i >= 0; i--) { temp *= A[i + 1]; B[i] *= temp; } return B; } };

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10187986.html