我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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
其他回答
下面是我使用python的简洁解决方案。
from functools import reduce
def excludeProductList(nums_):
after = [reduce(lambda x, y: x*y, nums_[i:]) for i in range(1, len(nums_))] + [1]
before = [1] + [reduce(lambda x, y: x*y, nums_[:i]) for i in range(1, len(nums_))]
zippedList = list(zip(before, after))
finalList = list(map(lambda x: x[0]*x[1], zippedList))
return finalList
我用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[] 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];
}
}
}
这是O(n²)但f#太漂亮了
List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed)
[1;1;1;1;1]
[1..5]
试试这个!
import java.util.*;
class arrProduct
{
public static void main(String args[])
{
//getting the size of the array
Scanner s = new Scanner(System.in);
int noe = s.nextInt();
int out[]=new int[noe];
int arr[] = new int[noe];
// getting the input array
for(int k=0;k<noe;k++)
{
arr[k]=s.nextInt();
}
int val1 = 1,val2=1;
for(int i=0;i<noe;i++)
{
int res=1;
for(int j=1;j<noe;j++)
{
if((i+j)>(noe-1))
{
int diff = (i+j)-(noe);
if(arr[diff]!=0)
{
res = res * arr[diff];
}
}
else
{
if(arr[i+j]!=0)
{
res= res*arr[i+j];
}
}
out[i]=res;
}
}
//printing result
System.out.print("Array of Product: [");
for(int l=0;l<out.length;l++)
{
if(l!=out.length-1)
{
System.out.print(out[l]+",");
}
else
{
System.out.print(out[l]);
}
}
System.out.print("]");
}
}
