首页 > 试题广场 >

构建乘积数组

[编程题]构建乘积数组
  • 热度指数:311487 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给定一个数组 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[i] 以外的全部元素的的乘积)。程序中不能使用除法。(注意:规定 B[0] = A[1] * A[2] * ... * A[n-1],B[n-1] = A[0] * A[1] * ... * A[n-2])
对于 A 长度为 1 的情况,B 无意义,故而无法构建,用例中不包括这种情况。

数据范围: ,数组中元素满足
示例1

输入

[1,2,3,4,5]

输出

[120,60,40,30,24]
示例2

输入

[100,50]

输出

[50,100]
推荐
<分析>:
解释下代码,设有数组大小为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 回复(54)
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 回复(25)
分两步: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 回复(14)
动态规划
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[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 回复(89)
很简单。
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 回复(5)
借助两个数组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 回复(3)
        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)
构造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 回复(5)

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 回复(1)
借鉴借鉴。自己打上一些注释。
import java.util.ArrayList;
public class Solution {
    //    ---------------------
    // B0 | 1  | A1 | A2 | A3 |
    //    ---------------------
    // B1 | A0 | 1  | A2 | A3 |
    //    ---------------------
    // B2 | A0 | A1 | 1  | A3 |
    //    ---------------------
    // B3 | A0 | A1 | A2 | 1  |
    //    ---------------------
    //以上面的4*4数组为例
    //B0 = A1*A2*A3,B1 = A0*A2*A3,B2 = A0*A1*A3,B3 = A0*A1*A2
    //第一轮,先算左下角的元素,即
    //B0 = 1,B1 = A0,B2 = A0*A1,B3 = A0*A1*A2
    //第二轮,再端右上角的元素,即
    //B2 = A0*A1* A3(temp=A3),B1 = A0* A2*A3(temp=A3*A2),B0 = A1*A2*A3(temp=A3*A2*A1)
    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;
    }
}

编辑于 2018-04-28 16:52:54 回复(0)
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)
B[j]=(A[0]~A[j-1]) * (A[j+1]~A[n-1])  
思路是:在0~n的循环体里,同时标记从前往后的乘积  和  从后往前的乘积;遇到完整的前半部分或后半部分了就放到B里去乘。
这样做的好处是每个B的元素共享了累乘的过程。
 int sumF = 1,sumB = 1,n = A.size();
        vector<int> B(n,1);
        for(int i = 0;i <n;i++)
        {
            B[i] *= sumF;//前半部分
            B[n- i -1] *= sumB;//后半部分
            
            sumF *= A[i];//标记从前往后累乘
            sumB *= A[n-i-1];//标记从后往前累乘
            
        }


发表于 2020-04-24 18:28:21 回复(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)
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)
import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int len=A.length;
        int[] b=new int[len];
        for(int i=0;i<len;i++){
            b[i]=1;
            for(int j=0;j<len;j++){
                if(j==i) continue;
                b[i]*=A[j];
            }
        }
        return b;
    }
}


发表于 2021-06-19 21:09:49 回复(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)
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)