我在一次工作面试中被问到这个问题，我想知道其他人是如何解决这个问题的。我最擅长使用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)中不使用除法来做这个。
当前回答
上下两次。在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;
}
其他回答
鬼鬼祟祟地绕过“不划分”规则:
sum = 0.0
for i in range(a):
sum += log(a[i])
for i in range(a):
output[i] = exp(sum - log(a[i]))
左旅行->右和保持保存产品。称之为过去。- > O (n) 旅行右->左保持产品。称之为未来。- > O (n) 结果[i] =过去[i-1] *将来[i+1] -> O(n) 过去[-1]= 1;和未来(n + 1) = 1;
O(n)
下面是一个使用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)。
O(n)时间的简洁解:
对于每个元素，计算在它之前出现的所有元素的乘积，并将其存储在数组“pre”中。 对于每个元素，计算该元素之后所有元素的乘积，并将其存储在数组“post”中 为元素i创建一个最终数组result， 结果[i] = pre[i-1]*post[i+1];
我的第一次尝试，用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]
