我在一次工作面试中被问到这个问题,我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
我们可以先从列表中排除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]
我用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]));
def productify(arr, prod, i):
if i < len(arr):
prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
retval = productify(arr, prod, i + 1)
prod[i] *= retval
return retval * arr[i]
return 1
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
prod = []
productify(arr, prod, 0)
print(prod)