我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。


当前回答

ruby的解决方案

a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result

其他回答

以下是线性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))

}

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

O(n)时间的简洁解:

对于每个元素,计算在它之前出现的所有元素的乘积,并将其存储在数组“pre”中。 对于每个元素,计算该元素之后所有元素的乘积,并将其存储在数组“post”中 为元素i创建一个最终数组result, 结果[i] = pre[i-1]*post[i+1];

我的第一次尝试,用Python。O (2 n):

def product(l):
    product = 1
    num_zeroes = 0
    pos_zero = -1

    # Multiply all and set positions
    for i, x in enumerate(l):
        if x != 0:
            product *= x
            l[i] = 1.0/x
        else:
            num_zeroes += 1
            pos_zero = i

    # Warning! Zeroes ahead!
    if num_zeroes > 0:
        l = [0] * len(l)

        if num_zeroes == 1:
            l[pos_zero] = product

    else:
        # Now set the definitive elements
        for i in range(len(l)):
            l[i] = int(l[i] * product)

    return l


if __name__ == "__main__":
    print("[0, 0, 4] = " + str(product([0, 0, 4])))
    print("[3, 0, 4] = " + str(product([3, 0, 4])))
    print("[1, 2, 3] = " + str(product([1, 2, 3])))
    print("[2, 3, 4, 5, 6] = " + str(product([2, 3, 4, 5, 6])))
    print("[2, 1, 2, 2, 3] = " + str(product([2, 1, 2, 2, 3])))

输出:

[0, 0, 4] = [0, 0, 0]
[3, 0, 4] = [0, 12, 0]
[1, 2, 3] = [6, 3, 2]
[2, 3, 4, 5, 6] = [360, 240, 180, 144, 120]
[2, 1, 2, 2, 3] = [12, 24, 12, 12, 8]

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

诀窍是构造数组(在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];
}

根据Billz的回答——抱歉我不能评论,但这里是一个正确处理列表中重复项的scala版本,可能是O(n):

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

返回:

List(1008, 144, 336, 336, 252, 252)