我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用Java,但也欢迎使用其他语言的解决方案。

给定一个数字数组nums,返回一个数字数组products,其中products[i]是所有nums[j]的乘积,j != i。 输入:[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)中不使用除法来做这个。


当前回答

以下是线性O(n)时间内的简单Scala版本:

def getProductEff(in:Seq[Int]):Seq[Int] = {

   //create a list which has product of every element to the left of this element
   val fromLeft = in.foldLeft((1, Seq.empty[Int]))((ac, i) => (i * ac._1, ac._2 :+ ac._1))._2

   //create a list which has product of every element to the right of this element, which is the same as the previous step but in reverse
   val fromRight = in.reverse.foldLeft((1,Seq.empty[Int]))((ac,i) => (i * ac._1,ac._2 :+ ac._1))._2.reverse

   //merge the two list by product at index
   in.indices.map(i => fromLeft(i) * fromRight(i))

}

这是可行的,因为本质上答案是一个数组,它是左右所有元素的乘积。

其他回答

多基因润滑剂方法的一个解释是:

诀窍是构造数组(在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];
int 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
int p = 1;
for (int i = 0; i < N; ++i) {
    products[i] = p;
    p *= a[i];
}

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

php版本 使用不除法的array_product函数。 如果我们将i的值临时设为1,那么数组product将完全满足我们的需要

<?php
function product($key, $arr)
{
    $arr[$key] = 1;
    return array_product($arr);
};
$arr = [1, 2, 3, 4, 5];
$newarr = array();


foreach ($arr as $key => $value) {

    $newarr[$key] = product($key, $arr);
}
print_r($newarr);

下面是Ruby中的一行程序解决方案。

全国矿工工会。映射{|n| (num - [n]).inject(:*)}

还有一个解决方案,使用除法。有两次遍历。 把所有元素相乘,然后除以每个元素。

下面是另一个简单的概念,可以解决O(N)中的问题。

        int[] arr = new int[] {1, 2, 3, 4, 5};
        int[] outArray = new int[arr.length]; 
        for(int i=0;i<arr.length;i++){
            int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
            outArray[i] = res/arr[i];
        }
        System.out.println(Arrays.toString(outArray));