我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
鬼鬼祟祟地绕过“不划分”规则:
sum = 0.0
for i in range(a):
sum += log(a[i])
for i in range(a):
output[i] = exp(sum - log(a[i]))
其他回答
我们可以先从列表中排除nums[j](其中j != i)，然后得到其余部分的乘积;下面是python解决这个难题的方法:
from functools import reduce
def products(nums):
return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))
[out]
[120, 60, 40, 30, 24]
技巧:
使用以下方法:
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，但这是解决它的方法。
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
int[] result = { 1, 1, 1, 1, 1 };
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
result[i] *= arr[j];
}
for (int k = arr.length - 1; k > i; k--) {
result[i] *= arr[k];
}
}
for (int i : result) {
System.out.println(i);
}
}
我想出了这个解决方案，我发现它很清楚，你觉得呢!?
左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;
O(n)
我用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]));
