给定一个整数数组，比如3，5，7，9。您需要创建另一个数组，并将其填充，使第二个数组的第0个位置是第一个数组中除了该位置上的数字之外所有数字的乘积，即应为5x7x9（不包括3），第二个数组第1个位置上的数字将是3x7x9（不包括5）。
我最初想到的答案是使用两个for循环，这将导致时间复杂度为O(n2)。后来我想到了以下方法：
先将第一个数组中所有数字相乘(3x5x7x9)，然后在填充第二个数组时，用这个乘积除以该位置上的数字。如果要填充第0个位置，则除以3，如果要填充第1个位置，则除以5，依此类推。这将把复杂度从O(n2)降至O(2n)。
但是，面试官说不允许使用除法。我除了将不同的可能乘积存储在某种数据结构中并在填充时使用之外，再也想不出其他办法了。最后当被问及答案时，他说他会维护两个前向和后向乘积数组。当被问及解决方案的空间复杂度问题时，他表示可以优化。
i-1 和 i+1，而不是 i 和 i，但我也没有再次检查。让我们使用你的例子：original-array =[3,5,7,9] first-array =[3,15,105,945] second-array =[945,315,63,9] 所以final-array =[1315,363,159,9451]（我假设越界索引值为1）。那将是正确的解决方案。 - davinO(n)。虽然这个解决方案在时间和空间复杂度上有更高的常数，但复杂度本身是相同的。 - davin
将元素1到i的乘积存储到数组A中，其中
A[i]表示元素1到元素i的乘积；将元素i到n（输入大小）的乘积存储到数组B中，其中
B[i]表示元素i到元素n的乘积；需要结果[i]时，使用A[i-1]*B[i+1]。这种方式可以处理边界情况，只需使用B[1]和A[n-2]（其中A[n-1]为最后一个元素）。
我认为可以在O(n log n)的时间复杂度内完成。
存储前一半数字和后一半数字的乘积。
还要存储第一季度、第二季度、第三季度和第四季度的乘积。
还要存储第一八分之一、第二八分之一、...第8个八分之一的乘积。
以此类推。
您可以通过计算每对数的乘积，然后计算每个“那些”对的乘积，从而从底层构建它。
这里的额外数据总量为O(n)，需要O(n)来计算（易于证明）。
现在，要计算（例如）元素0的输出，您需要取第二个一半的乘积，第一个四分之一的第二个一半的乘积等等，并将它们相乘。 这样的数字有log n个，因此此操作为log n。
要计算元素k的乘积，请将k写成二进制并翻转其位。 高位告诉您从哪一半开始；下一位告诉您下一步使用剩余一半的哪一半；下一位告诉您下一步使用剩余四分之一的哪一半；以此类推。
因此，任何输出元素都可以在log n时间内计算。 对于每个n个输出元素执行此操作，您将获得O(n log n)。
[编辑]
当然，“前向和后向倍增”方法也可行。 我想我应该认真阅读问题。 :-)
[编辑2]
至于面试官（和davin）的解决方案，您实际上不需要构建额外的数组... 假设您可以编辑输出数组中的值。
首先，构造输出数组B，使得B[i] = A[0]A[1]...*A[i-1]，而B[0]=1。 您可以逐步完成此操作，因此这是线性时间：
B[0] = 1;
for (i=1 ; i < n ; ++i) {
B[i] = B[i-1] * A[i];
}
x = A[n-1];
for (j=n-2 ; j >= 0 ; ++j) {
B[j] *= x;
x *= A[j];
}
我相信他的意思是，给定一个数组A={a_1, ..., a_n}，他将创建两个新数组：
F_A={a_1, a_1 * a_2, ..., a_1 * ... * a_n}
可以通过在数组上向前迭代时维护累积乘积来线性时间构建，
B_A={a_1 * ... * a_n, ..., a_n * a_(n-1), a_n}
可以通过在数组上向后迭代时维护累积乘积来线性时间构建。
现在，要填充结果数组中的索引i，只需将F_A[i-1]与B_A[i+1]相乘：
F_A[i-1] * B_A[i+1] = [a_1 * ... * a_(i-1)] * [a_(i+1) * ... * a_n]
滥用对数怎么样？你可以用减法代替除法。
但是如果你可以修改第一个数组，你可以做一些像这样的事情
//pop arr2
r=1
for(i=len-1;i>=0;i--)
{
r=r*arr1[i]
arr2[i]=r
}
//modify arr1
r=1
for(i=0;i<len;i++)
{
r=r*arr1[i]
arr1[i]=r
}
//fix arr2
arr2[0]=arr2[1];
for(i=1;i<len-1;i--)
{
arr2[i]=arr2[i+1]*arr1[i-1];
}
arr2[len-1]=arr1[len-2];
O(n)，而解决方案添加了另一个O(n)，总体仍然是O(n)。 - davin