剑指offer：构建乘积数组

题目描述：

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

思路分析：

思路一：由于不能使用除法，首先想到的就是对于A中每个元素用遍历的方式，去判断是否要乘到B数组的对应位置，这样的时间复杂度为O(n^2)，超时。

思路二：用空间换时间，将B的构造分为两段，第一段为0到i-1，第二段为i+1到n，那么在构造第一段时，从前往后构造，B[i]=B[i-1]*A[i-1]；构造第二段时，从后往前构造，B[i]=B[i+1]*A[i+1]。最后将两段乘起来，即为最终所求的数组。

代码：

 class Solution {

 public:

     vector<int> multiply(const vector<int>& A) {

         int len = A.size();

         if(len<=)

             return A;

         vector<int> B(len, );

         vector<int> tmp(len, );

         for(int i=; i<len; i++)

             B[i] = B[i-]*A[i-];

         for(int i=len-; i>=; i--)

             tmp[i] = tmp[i+]*A[i+];

         for(int i=; i<len; i++)

             B[i] = B[i]*tmp[i];

         return B;

     }

 };

巴特西

剑指offer：构建乘积数组

最新文章

热门文章