[编程题]构建乘积数组

<分析>：

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];

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;
}
};

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;
}
}

//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;
}
};

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;
}
}

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

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;
}
}

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]）
....

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;
}
}

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;
}
}

# -*- 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

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;

}
};

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;
}

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;
}
};

## 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

# -*- 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

# -*- 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

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;
}
};

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;
}
};

/*复杂度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;
}

//唔…自觉做得还比较简单，既然不能用除法，就以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;
}
};

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; }

class Solution {
public:
vector<int> multiply(const vector<int>& A) {
int n=A.size(),j,sum;
vector<int> C=A;//C是A的复制，以便对A进行操作
vector<int> B=A;//要返回的结果，大小与A相同
for(int i=0;i<n;i++){
int s=C.front();
C.push_back(s);
C.erase(C.begin());
j=0,sum=1;
while(j<=n-2){
sum*=C[j];
j++;
}
B[i]=sum;
}
return B;
}
};

644条回答 56175浏览

# 通过挑战的用户

• 2019-10-17 03:38:14
• 2019-10-16 23:15:22
• 2019-10-16 22:57:01
• 2019-10-16 22:17:39
• 2019-10-16 21:41:07

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题