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