鉴于数字数组，返回的所有其它数字产品阵列（无分频） [英] Given an array of numbers, return array of products of all other numbers (no division)

问题描述

有人问我在面试这个问题，我想知道别人怎么会解决这个问题。我最熟悉的Java，但在其他语言的解决方案是值得欢迎的。

  

鉴于数字数组， NUMS ，返回数字数组产品，其中产品[I] 是所有 NUMS [J]产品，J！=我。

 输入：[1，2，3，4，5]
输出：[（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）不使用分部。

解决方案

polygenelubricants 方法的解释是： 关键是要构建阵列（的情况下为4元）

{1，[0]，A [0] * A [1]，A [0] * A [ 1] *一个[2]，} {一个[1] *一个[2] *一个[3]，A [2] *一个[3]，A [3]，1，}

这两者可以在O（n）的分别起始于左和右边缘进行。

然后乘以元素的两个数组元素给出所需的结果。

我的code会是这个样子：

INT A [N] //这是输入 INT products_below [N]; p为1; 的for（int i = 0; I＆LT; N ++我）{   products_below [i] = P;   P * = A [1]; } INT products_above [N]; p为1; 的for（int i = N-1; I＆GT; = 0; - 我）{   products_above [i] = P;   P * = A [1]; } INT产品[N]; //这是结果 的for（int i = 0; I＆LT; N ++我）{   产品[I] = products_below [我] * products_above [I] }

如果您需要O（1）在太空中也可以做到这一点（这是不太清楚恕我直言）

INT A [N] //这是输入 INT产品[N]; //获取产品目前股指下方 p为1; 的for（int i = 0; I＆LT; N ++我）{   产品[I] = P;   P * = A [1]; } //获取了短路电流指数高于产品 p为1; 的for（int i = N-1; I＆GT; = 0; - 我）{   产品[I] * = P;   P * = A [1]; }

I was asked this question in a job interview, and I'd like to know how others would solve it. I'm most comfortable with Java, but solutions in other languages are welcome.

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of 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]

You must do this in O(N) without using division.

解决方案

An explanation of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

{              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,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.

Then multiplying the two arrays element by element gives the required result

My code would look something like this:

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

If you need to be O(1) in space too you can do this (which is less clear IMHO)

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

这篇关于鉴于数字数组，返回的所有其它数字产品阵列（无分频）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！