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


当前回答

在这里添加我的javascript解决方案,因为我没有发现任何人建议这样做。 除法是什么,除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积,然后遍历每个元素,并减去当前元素直到0:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

其他回答

下面是我尝试用Java来解决这个问题。抱歉格式不规范,但代码有很多重复,这是我能做的最好的,使它可读。

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

循环不变量为pi = nums[0] * nums[1] *..* nums[N-2] *..num [j + 1]。左边的i部分是“前缀”逻辑,右边的j部分是“后缀”逻辑。


递归一行程序

Jasmeet给出了一个(漂亮的!)递归解;我把它变成了这样(可怕!)Java一行程序。它进行就地修改,堆栈中有O(N)个临时空间。

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

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

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

我们可以先从列表中排除nums[j](其中j != i),然后得到其余部分的乘积;下面是python解决这个难题的方法:

from functools import reduce
def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))

[out]
[120, 60, 40, 30, 24]

这个解决方案可以被认为是C/ c++的。 假设我们有一个包含n个元素的数组a 像a[n]一样,那么伪代码将如下所示。

for(j=0;j<n;j++)
  { 
    prod[j]=1;

    for (i=0;i<n;i++)
    {   
        if(i==j)
        continue;  
        else
        prod[j]=prod[j]*a[i];
  }

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

}

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