我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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想出了两个解决方案，一个有除法，一个没有
//不除法 函数methodOne(arr) { 加勒比海盗。Map (item => { 加勒比海盗。Reduce ((result, num) => { If (num !== item) { 结果=结果* num; ｝ 返回结果; }, 1) })； ｝ //使用除法 函数methodTwo(arr) { Var mul = arr。Reduce ((result, num) => { 结果=结果* num; 返回结果; }, 1) 加勒比海盗。Map (item => mul/item); ｝ console.log(methodOne([1,2,3,4,5])); console.log(methodTwo([1,2,3,4,5]));
其他回答
这是我的代码:
int multiply(int a[],int n,int nextproduct,int i)
{
int prevproduct=1;
if(i>=n)
return prevproduct;
prevproduct=multiply(a,n,nextproduct*a[i],i+1);
printf(" i=%d > %d\n",i,prevproduct*nextproduct);
return prevproduct*a[i];
}
int main()
{
int a[]={2,4,1,3,5};
multiply(a,5,1,0);
return 0;
}
我用Javascript想出了两个解决方案，一个有除法，一个没有
//不除法 函数methodOne(arr) { 加勒比海盗。Map (item => { 加勒比海盗。Reduce ((result, num) => { If (num !== item) { 结果=结果* num; ｝ 返回结果; }, 1) })； ｝ //使用除法 函数methodTwo(arr) { Var mul = arr。Reduce ((result, num) => { 结果=结果* num; 返回结果; }, 1) 加勒比海盗。Map (item => mul/item); ｝ console.log(methodOne([1,2,3,4,5])); console.log(methodTwo([1,2,3,4,5]));
ruby的解决方案
a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result
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);
根据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)
