我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
这里是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视图或迭代器进行惰性计算。
其他回答
左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;
O(n)
将Michael Anderson的解决方案翻译成Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
技巧:
使用以下方法:
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，但这是解决它的方法。
根据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)
O(n)时间的简洁解:
对于每个元素，计算在它之前出现的所有元素的乘积，并将其存储在数组“pre”中。 对于每个元素，计算该元素之后所有元素的乘积，并将其存储在数组“post”中 为元素i创建一个最终数组result， 结果[i] = pre[i-1]*post[i+1];
