我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
试试这个!
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("]");
}
}
其他回答
JavaScript中使用reduce的变体
const getProduct = arr => arr。Reduce ((acc, value) => acc * value); const arrayWithExclusion = (arr, node) => 加勒比海盗。Reduce ((acc, val, j) => (node !== j ?)[…Acc, val]: Acc)， []); const getproductwitheexclusion = arr => { Let result = []; 对于(设I = 0;I < arrr .length;I += 1) { 结果。推动(getProduct (arrayWithExclusion(加勒比海盗,我))); ｝ 返回结果; }；
还有一个解决方案，使用除法。有两次遍历。 把所有元素相乘，然后除以每个元素。
上下两次。在O(N)完成的工作
private static int[] multiply(int[] numbers) {
int[] multiplied = new int[numbers.length];
int total = 1;
multiplied[0] = 1;
for (int i = 1; i < numbers.length; i++) {
multiplied[i] = numbers[i - 1] * multiplied[i - 1];
}
for (int j = numbers.length - 2; j >= 0; j--) {
total *= numbers[j + 1];
multiplied[j] = total * multiplied[j];
}
return multiplied;
}
将Michael Anderson的解决方案翻译成Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
这里是Scala中的完整代码:
val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))
这将打印出以下内容:
120
60
40
30
24
程序将过滤掉当前的elem (_ != elem);并使用reducleft方法将新列表相乘。我认为这将是O(n)如果你使用scala视图或迭代器进行惰性计算。
