给定一个数字数组，返回所有其他数字的乘积数组（无除法）

一尘不染

给定一个数字数组，返回所有其他数字的乘积数组（无除法）

algorithm

在工作面试中有人问我这个问题，我想知道其他人会如何解决。我对Java最满意，但是欢迎使用其他语言的解决方案。

给定一个数字数组nums，则返回一个数字数组products，其中products[i]是all的乘积nums[j], j != i。
Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]
您必须在O(N)不使用除法的情况下进行此操作。

阅读 366

2020-07-28

共1个答案

一尘不染

多基因润滑剂方法的解释是：技巧是构造数组（对于4个元素而言）

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

两者都可以通过分别从左边缘和右边缘开始在O（n）中完成。

然后将两个数组元素相乘得到所需的结果

我的代码如下所示：

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i) {
  products[i]=products_below[i]*products_above[i];
}

如果您也需要在空间上设置O（1），则可以这样做（恕我直言，恕我直言）

int a[N] // This is the input
int products[N];

// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
  products[i]*=p;
  p*=a[i];
}

2020-07-28