给定一个数字数组，返回所有其他数字的乘积数组(无除法) [英] Given an array of numbers, return array of products of all other numbers (no division)

问题描述

我在求职面试中被问到这个问题，我想知道其他人会如何解决这个问题.我最熟悉 Java，但欢迎使用其他语言的解决方案.

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.

给定一个数字数组 nums，返回一个数字数组 products，其中 products[i] 是所有 products[i] 的乘积code>nums[j], j != i.

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]

你必须在 O(N) 中做到这一点，而不使用除法.

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

推荐答案

polygenelubricants 方法的解释是:诀窍是构造数组(在 4 个元素的情况下)

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

通过分别从左右边缘开始，两者都可以在 O(n) 中完成.

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

如果你也需要在空间中成为 O(1)，你可以这样做(恕我直言不太清楚)

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屋！