我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
技巧:
使用以下方法:
public int[] calc(int[] params) {
int[] left = new int[n-1]
in[] right = new int[n-1]
int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
fac1 = fac1 * params[i];
fac2 = fac2 * params[n-i];
left[i] = fac1;
right[i] = fac2;
}
fac = 1;
int[] results = new int[n];
for( int i=0; i<n; i++ ) {
results[i] = left[i] * right[i];
}
是的，我确定我错过了一些I -1而不是I，但这是解决它的方法。
其他回答
这个解决方案可以被认为是C/ c++的。 假设我们有一个包含n个元素的数组a 像a[n]一样，那么伪代码将如下所示。
for(j=0;j<n;j++)
{
prod[j]=1;
for (i=0;i<n;i++)
{
if(i==j)
continue;
else
prod[j]=prod[j]*a[i];
}
将Michael Anderson的解决方案翻译成Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
下面是另一个简单的概念，可以解决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));
根据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)
试试这个!
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("]");
}
}
