首页 > 试题广场 > 构建乘积数组
[编程题]构建乘积数组
给定一个数组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]。不能使用除法。
推荐
<分析>:
解释下代码,设有数组大小为5。
对于第一个for循环
第一步:b[0] = 1;
第二步:b[1] = b[0] * a[0] = a[0]
第三步:b[2] = b[1] * a[1] = a[0] * a[1];
第四步:b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第五步:b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];
然后对于第二个for循环
第一步
temp *= a[4] = a[4];  
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步
temp *= a[2] = a[4] * a[3] * a[2];  
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步
temp *= a[1] = a[4] * a[3] * a[2] * a[1];  
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];
由此可以看出从b[4]到b[0]均已经得到正确计算。
class Solution {
public:
  vector<int> multiply(const vector<int>& A) {
  vector<int> vec;
  int sz=A.size();
  if(sz==0)
   return vec;
  vec.push_back(1);
  for(int i=0;i<sz-1;i++)
   vec.push_back(vec.back()*A[i]);
  int tmp=1;
  for(int i=sz-1;i>=0;i--)
  {
   vec[i]=vec[i]*tmp;
   tmp=tmp*A[i];
  }
  return vec;
    }
};

编辑于 2015-08-25 11:17:49 回复(42)
剑指的思路:
B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得,上三角,从下向上也是连乘。
因此我们的思路就很清晰了,先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。

public class Solution {
    public int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        if(length != 0 ){
            B[0] = 1;
            //计算下三角连乘
            for(int i = 1; i < length; i++){
                B[i] = B[i-1] * A[i-1];
            }
            int temp = 1;
            //计算上三角
            for(int j = length-2; j >= 0; j--){
                temp *= A[j+1];
                B[j] *= temp;
            }
        }
		return B;
    }
}

发表于 2016-08-29 16:43:17 回复(67)
L0L头像 L0L
//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
//从左到右算 B[i]=A[0]*A[1]*...*A[i-1]
//从右到左算B[i]*=A[i+1]*...*A[n-1] 
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
    
    	int n=A.size();
    	vector<int> b(n);
    	int ret=1;
    	for(int i=0;i<n;ret*=A[i++]){
    		b[i]=ret;
		}
		ret=1;
		for(int i=n-1;i>=0;ret*=A[i--]){
			b[i]*=ret;
		}
    	return b;
    }
};

发表于 2015-09-24 10:10:18 回复(17)
分两步:1.计算前i - 1个元素的乘积,及后N - i个元素的乘积分别保存在两个数组中。这可以用动态           规划实现。
        2.计算B[i]的值。
import java.util.ArrayList;
public class Solution {
    int[] multiply(int[] A) {
        int len = A.length;
        int forword[] = new int[len];
        int backword[] = new int[len];
        int B[] = new int[len];
        forword[0] = 1;
        backword[0] = 1;
        for(int i = 1;i < len; i++){
            forword[i] = A[i - 1]*forword[i-1];
            backword[i] = A[len - i]*backword[i - 1];
        }
        for(int i = 0; i < len; i++){
            B[i] = forword[i] * backword[len - i -1];
        }
        return B;
    }
}
 

发表于 2015-06-29 22:58:16 回复(13)

思路:按上图把每行被1分割的两部分乘积都计算出来,这样可以从首尾分别用累乘算出两个列表,然后两个列表首尾相乘就是B的元素

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        head = [1]
        tail = [1]
        for i in range(len(A)-1):
            head.append(A[i]*head[i])
            tail.append(A[-i-1]*tail[i])
        return [head[j]*tail[-j-1] for j in range(len(head))]

编辑于 2018-02-14 14:04:07 回复(2)
动态规划
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        if(A==null||A.length==0)
            return A;
		int[] left = new int[A.length];//记录除了自己,左边的乘积
        int[] right = new int[A.length];//记录除了自己,右边的乘积
        right[A.length-1] = 1;
        for(int i = A.length-2;i>=0;i--){
            right[i] = right[i+1]*A[i+1];
        }
        left[0] = 1;
        for(int i = 1;i<A.length;i++){
            left[i] = left[i-1]*A[i-1];
        }
        int[] B = new int[A.length];
        for(int i = 0;i<A.length;i++){
            B[i] = left[i]*right[i];
        }
        return B;
    }
}

发表于 2016-04-17 17:58:08 回复(2)
很简单。
B[0] = A[1] * A[2] * A[3] * A[4] *....*A[n-1] ;(没有A[0])
B[1 ]= A[0] * A[2] * A[3] * A[4] *....*A[n-1] ;(没有A[1])
B[2] = A[0] * A[1] * A[3] * A[4] *....*A[n-1] ;(没有A[2])
....
即B[i]项等于A数组所有数的乘积,但是去除A[i]项。由于是乘法,所以直接令A[i]项等于1即可。
代码中加个flag标志做判断即可。
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
		int[] B = new int[A.length];
        boolean changed = false;
        for(int k = 0; k < B.length; k++){
            B[k] = 1;
            for(int i = 0; i < A.length; i++){
                int temp = 1;
                if(i == k){
                    changed = true;
                    temp = A[i];
                    A[i] = 1;
                }
                B[k] *= A[i];
                if(changed){
                    A[i] =temp;
                    changed = false;
                }
            }
            
        }
        return B;
    }
}



发表于 2017-07-28 09:48:24 回复(4)
借助两个数组lefts和rights,一个记录B[i]值的左乘结果A[0]*A[1]*...*A[i-1],一个记录B[i]值的右乘结果A[i+1]*A[i+2]*...*A[n-1],然后B[i]=lefts[i]*rights[i];
public class Solution {
    public int[] multiply(int[] A) {
        int len = A.length;
		int[] lefts = new int[len];
		int[] rights = new int[len];
		lefts[0] = lefts[len-1] = rights[0] = rights[len-1] = 1;
		int l = 1;
		int r = 1;
		for (int i=1; i<len; i++){
			lefts[i] = A[i-1]*lefts[i-1];
		}
		
		for (int i=len-2; i>=0; i--){
			rights[i] = A[i+1]*rights[i+1];
		}
		int[] B = new int[len];
		while (len>0){
			len--;
			B[len] = lefts[len]*rights[len];
		}
		return B;
    }
}

发表于 2017-07-22 23:06:53 回复(1)
构造c=A,每次算之前把c[i]=1,然后算所有c的乘积给b[i]然后再让c[i]=A[i] ,i++
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n=A.size();
        int k=n;
    	vector<int> b;
        vector<int> c;
        for(int i=0;i<n;i++){
            c.push_back(A[i]);
        }
        for(int i=0;i<n;i++){
            b.push_back(1);
        }
        for(int i=0;i<n;i++){
            c[i]=1;
            k=n;
            for(int j=0;j<n;j++){
                b[i]*=c[j];
            }
            c[i]=A[i];
        }
        return b;
        
    }
};

发表于 2017-03-28 22:17:53 回复(2)
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        B = []

        for i in range(len(A)):
            temp = A[i]
            b= 1
            for j in range(len(A)):
                A[i] = 1
                b*=A[j]
            B.append(b)
            A[i] = temp
        return B

发表于 2017-08-20 20:38:55 回复(2)
class Solution 
{
public:
    vector<int> multiply(const vector<int>& A) 
    {
     /*   vector<int> B;//直接暴力解决,逐行遍历,然后逐个相乘
        if (!A.empty())
        {
            int n = A.size();
            for (int i = 0; i <= n - 1; i++)
            {     
                int mult = 1;
                for (int j = 0; j <= n - 1; j++)
                {
                    if (j != i)
                        mult *= A[j];
                }
                B.push_back(mult);
            }
        }
        return B;*/
        vector<int> B;//剑指offer思路,总结规律,使用递推公式求解
        if (!A.empty())
        {
            int n = A.size();
            vector<int> C, D;
            B.assign(n, 1);
            C.assign(n, 1);
            D.assign(n, 1);
            if (n > 1)
            {
                C[1] = A[0];
                D[n - 2] = A[n - 1];
            }
            for (int i = 2; i <= n - 1; i++)
                C[i] = C[i - 1] * A[i - 1];  
            for (int i = n - 3; i >= 0; i--)
                D[i] = D[i + 1] * A[i + 1];
            for (int i = 0; i < n; i++)
                B[i] = C[i] * D[i];
        }
        return B;
    }
};

发表于 2017-07-18 01:52:24 回复(0)
        public static int[] multiply(int[] A) {
		if(A == null){
			return null;
		}
		int len = A.length;
		int[] forword = new int[len];
		int[] back = new int[len];
		int[] B = new int[len];
		forword[0] = 1;
		back[len - 1] = 1;
		for(int i = 1; i < len; i++){
			forword[i] = A[i - 1] * forword[i - 1];
		}
		for(int i = len - 2; i >= 0; i--){
			back[i] = A[i + 1] * back[i + 1];
		}
		for(int i = 0; i < len; i++){
			B[i] = forword[i] * back[i];
		}
		return B;
	}

编辑于 2016-04-26 14:31:36 回复(0)
特别要注意的是list b=list a会改变list a 的值,新的变量和原来的变量实际上指向的是同一个地址,等号连接起来的变量互相影响。 所以要使用copy函数,必须时可以使用deepcopy。
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        import copy
        # write code here
        B=[1]*len(A)
        for i in range(len(A)):
            C=copy.copy(A)
            C.pop(i)
            for j in range(len(C)):
                B[i]*=C[j]
        return B

编辑于 2018-05-05 09:59:44 回复(1)

Python Solution

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        B=[i for i in range(len(A))]
        for i in B:
            B[i]=1  # 将B中的元素每次初始化为1
            for j in (A[:i]+A[i+1:]):  # 遍历A中除了i以外的所有元素
                B[i]*=j
        return B
发表于 2019-08-03 12:03:33 回复(0)
# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        A1 = [1 for i in A]
        A2 = [1 for i in A]
        B = [1 for i in A]
        for i in range(1,len(A)):
            A1[i] = A1[i-1] * A[i-1]
        for i in range(len(A)-2,-1,-1):
            A2[i] = A2[i+1] * A[i+1]
        for i in range(len(A)):
            B[i] = A1[i] * A2[i]
        return B
发表于 2019-06-03 22:51:33 回复(0)
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
    	vector<int> B(n, 1);
        vector<int> C(n, 1);
        vector<int> D(n, 1);
        for(int i = 1; i < n; ++i){
            C[i] = C[i-1]*A[i-1];
            D[i] = D[i-1]*A[n-i];
        }
        for(int i = 0; i < n; ++i)
            B[i] = C[i]*D[n-1-i];
		return B;
    }
};

发表于 2017-08-12 14:51:21 回复(0)
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
       vector<int> vec;
       vec.push_back(1);
       for(int i=1;i<A.size();i++)
       {
           int temp=A[i-1]*vec[i-1];
           vec.push_back(temp);
       }
       int temp=1;
       for(int i=A.size()-2;i>=0;--i)
       {
           temp =temp*A[i+1];
           vec[i]=vec[i]*temp;
       }
        return vec;
    }
};

发表于 2016-07-25 14:37:02 回复(0)
Ron头像 Ron
	/*复杂度O(n)*/
         int[] multiply(int[] A) {
		int length = A.length;
		int[] B = new int[length];
		if(length <= 0)
			return B;
		int[] before = new int[length];
		int[] after = new int[length];
		before[0] = 1;
		after[0] = 1;
		for(int i = 0 ; i < length; i ++){
			if(i > 0)
				before[i] = before[i-1]*A[i-1];
			if(i < length-1)
				after[i+1] = after[i]*A[length-i-1];
		}
		for(int i = 0; i < length; i ++){
			B[i] = before[i]*after[length-i-1];
		}
		return B;
	}

编辑于 2015-07-11 17:28:01 回复(0)
//唔…自觉做得还比较简单,既然不能用除法,就以i为界限分为两部分来计算
class Solution {
public:
    vector<int> multiply(const vector<int>& A) 
    {
        vector<int> B;
        for (unsigned int i=0; i<A.size(); ++i)
        {            
            int Temp1 = 1, Temp2 = 1;
            for (unsigned int k=0; k<i; ++k)
                Temp1 *= A[k];
            for (unsigned int m=i+1; m<A.size(); ++m)
                Temp2 *= A[m];
            B.push_back(Temp1 * Temp2);
        }
        return B;    
    }
};

发表于 2016-09-13 21:06:43 回复(1)
public: vector<int> multiply(const vector<int>& A) { vector<int> B; int length = A.size(); if(length==0) return B; B.push_back(1); for(int i=0;i<length-1;++i) { B.push_back(B.back()*A[i]); } int temp = 1; for(int i=length-2;i>=0;--i) { temp *= A[i+1]; B[i] *=temp; } return B; }
发表于 2016-03-26 15:19:24 回复(0)
1. 暴力遍历,时间复杂度为O(N2)
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        if (A.empty()) return result;
        for (int i = 0; i < (int)A.size();++i) {
            int temp = 1;
            for (int j = 0; j < (int)A.size(); ++j) {
                if (j != i) {
                    temp *= A[j];
                }
            }
            result.push_back(temp);
        }
        
        return result;
    }
};
2. 使用矩阵的上三角和下三角的性质,不借助辅助空间,时间复杂度为O(N)
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> result;
        if (A.empty())  return result;
        int length = A.size();
        result.push_back(1);
        for (int i = 1; i < length; ++i) {
            result.push_back(result.back() * A[i - 1]);
        }
        
        int temp = 1;
        for (int i = length - 2; i >= 0; --i) {
            temp = temp * A[i + 1];
            result[i] = result[i] * temp;
        }
        
        return result;
    }
};



发表于 2019-08-15 19:03:20 回复(0)