我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
这是我的代码:
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;
}
这是我的代码:
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;
}
下面是另一个简单的概念,可以解决O(N)中的问题。
int[] arr = new int[] {1, 2, 3, 4, 5};
int[] outArray = new int[arr.length];
for(int i=0;i<arr.length;i++){
int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
outArray[i] = res/arr[i];
}
System.out.println(Arrays.toString(outArray));