在工作面试中有人问我这个问题,我想知道其他人会如何解决。我对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)不使用除法的情况下进行此操作。
给定一个数字数组nums,则返回一个数字数组products,其中products[i]是all的乘积nums[j], j != i。
nums
products
products[i]
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)不使用除法的情况下进行此操作。
O(N)
多基因润滑剂方法的解释是:技巧是构造数组(对于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]; }