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

}

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

其他回答

import java.util.Arrays;

public class Pratik
{
    public static void main(String[] args)
    {
        int[] array = {2, 3, 4, 5, 6};      //  OUTPUT: 360  240  180  144  120
        int[] products = new int[array.length];
        arrayProduct(array, products);
        System.out.println(Arrays.toString(products));
    }

    public static void arrayProduct(int array[], int products[])
    {
        double sum = 0, EPSILON = 1e-9;

        for(int i = 0; i < array.length; i++)
            sum += Math.log(array[i]);

        for(int i = 0; i < array.length; i++)
            products[i] = (int) (EPSILON + Math.exp(sum - Math.log(array[i])));
    }
}

输出:

[360, 240, 180, 144, 120]

时间复杂度:O(n) 空间复杂度:O(1)

    int[] arr1 = { 1, 2, 3, 4, 5 };
    int[] product = new int[arr1.Length];              

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < product.Length; j++)
        {
            if (i != j)
            {
                product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
            }
        }
    }

这里是Scala中的完整代码:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

这将打印出以下内容:

120
60
40
30
24

程序将过滤掉当前的elem (_ != elem);并使用reducleft方法将新列表相乘。我认为这将是O(n)如果你使用scala视图或迭代器进行惰性计算。

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);

在这里添加我的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;
}