我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] product = new int[arr1.Length];
for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < product.Length; j++)
{
if (i != j)
{
product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
}
}
}
其他回答
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] product = new int[arr1.Length];
for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < product.Length; j++)
{
if (i != j)
{
product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
}
}
}
在这里添加我的javascript解决方案，因为我没有发现任何人建议这样做。 除法是什么，除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积，然后遍历每个元素，并减去当前元素直到0:
//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
var res = [];
var totalProduct = 1;
//calculate the total product
for(var i = 0; i < input.length; i++){
totalProduct = totalProduct * input[i];
}
//populate the result array by "dividing" each value
for(var i = 0; i < input.length; i++){
var timesSubstracted = 0;
var divisor = input[i];
var dividend = totalProduct;
while(divisor <= dividend){
dividend = dividend - divisor;
timesSubstracted++;
}
res.push(timesSubstracted);
}
return res;
}
下面是一个使用c#的函数式示例:
Func<long>[] backwards = new Func<long>[input.Length];
Func<long>[] forwards = new Func<long>[input.Length];
for (int i = 0; i < input.Length; ++i)
{
var localIndex = i;
backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
}
var output = new long[input.Length];
for (int i = 0; i < input.Length; ++i)
{
if (0 == i)
{
output[i] = forwards[i + 1]();
}
else if (input.Length - 1 == i)
{
output[i] = backwards[i - 1]();
}
else
{
output[i] = forwards[i + 1]() * backwards[i - 1]();
}
}
我不完全确定这是O(n)，因为所创建的Funcs是半递归的，但我的测试似乎表明它在时间上是O(n)。
我的第一次尝试，用Python。O (2 n):
def product(l):
product = 1
num_zeroes = 0
pos_zero = -1
# Multiply all and set positions
for i, x in enumerate(l):
if x != 0:
product *= x
l[i] = 1.0/x
else:
num_zeroes += 1
pos_zero = i
# Warning! Zeroes ahead!
if num_zeroes > 0:
l = [0] * len(l)
if num_zeroes == 1:
l[pos_zero] = product
else:
# Now set the definitive elements
for i in range(len(l)):
l[i] = int(l[i] * product)
return l
if __name__ == "__main__":
print("[0, 0, 4] = " + str(product([0, 0, 4])))
print("[3, 0, 4] = " + str(product([3, 0, 4])))
print("[1, 2, 3] = " + str(product([1, 2, 3])))
print("[2, 3, 4, 5, 6] = " + str(product([2, 3, 4, 5, 6])))
print("[2, 1, 2, 2, 3] = " + str(product([2, 1, 2, 2, 3])))
输出:
[0, 0, 4] = [0, 0, 0]
[3, 0, 4] = [0, 12, 0]
[1, 2, 3] = [6, 3, 2]
[2, 3, 4, 5, 6] = [360, 240, 180, 144, 120]
[2, 1, 2, 2, 3] = [12, 24, 12, 12, 8]
我们正在分解数组的元素，首先从下标之前开始，即前缀，然后是下标或后缀之后
class Solution:
def productExceptSelf(nums):
length = len(nums)
result = [1] * length
prefix_product = 1
postfix_product = 1
# we initialize the result and products
for i in range(length)
result[i] *= prefix_product
prefix_product *= nums[i]
#we multiply the result by each number before the index
for i in range(length-1,-1,-1)
result[i] *= postfix_product
postfix_product *= nums[i]
#same for after index
return result
抱歉，走路时用手机
