有一个整数数组，比方说3,5,7,9。您应该创建另一个数组并填充它，使得第二个数组的第0个位置应该是第一个数组中所有数字的乘积，不包括第0个位置的数字，这意味着它应该是5x7x9（不包括3），索引处的数字第二个阵列中的1个将是3x7x9（不包括5）的乘积。
我想到的第一个答案是有2个for循环，这将导致O（n2）的时间复杂度。后来我想到了这个：
将第一个数组中的所有数字相乘（3x5x7x9），并在填充第二个数组时，我将该产品除以该位置的数字。如果我填充第0个位置则除以3，如果我填充第1个位置则除以5，依此类推。这会降低从O（n2）到O（2n）的复杂性。
但采访者表示不允许分裂。除了将不同的可能倍数存储在某种数据结构中并在填充时使用它，我想不出别的。我放弃了，但当被问到答案时，他说他将维持2个向前和向后的多重阵列。当被问及解决方案的空间复杂性问题时，他说可以对其进行优化。
我不确定问题是关于空间还是关于解决方案本身。由于每个人都提供解决方案，这让我觉得他们不理解面试官的解决方案，所以这里有一个解释：
我们维护两个数组。第一个是原始数组的运行产品。所以元素到位 i 将是第一个产品 i 原始数组中的元素（没有乳胶，但是 i日 进入有价值 pi{j=0 to i} j）。第二个数组只是反方向，所以 i日 进入将有价值： pi{j=N-i to N} j。
要构造所需的最终数组，我们只需运行两个数组中的每一个并乘以条目。所以 i日 最终数组中的值，将是所有条目的乘积，这是其中的乘积 0 至 i-1 时代的产物 i+1 至 N，这是第一个阵列的产物 i-1 条目和第二个数组 i+1 条目。
总时间和空间 O(n)
将元素1到i的产品存储到一个数组中
A，与A[i]是元素1到元素i的产物;将元素i到n（输入大小）的产品存储到一个数组中
B，与B[i]是元素i到元素n的产物;当需要result [i]时，使用A [i-1] * B [i + 1]。角落案件是 这样简单，只需使用B [1]和A [n-2]（A [n-1]是最后一个 元件）。
我想我可以在O（n log n）中完成。
存储数字前半部分和后半部分数字的乘积。
还存储第一季度，第二季度，第三季度和第四季度的产品。
还存储第八，第二，第八，......第八八的产品。
等等。
您可以通过计算每对产品，然后是每个产品的产品，从头开始构建它 那些 对，等等。
这里额外数据的总量是O（n）并且需要O（n）来计算（易于显示）。
现在，为了计算（比如）元素0的输出，你可以得到下半年的产品，即第二季度的产品（即第一季度的下半年），第八季度的下半年的产品等等，并将它们相乘。有这样的数字，所以这个操作是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];
}
接下来，扫描 向后 从n-2计算答案，跟踪“到目前为止的产品”：
x = A[n-1];
for (j=n-2 ; j >= 0 ; ++j) {
B[j] *= x;
x *= A[j];
}
这解决了O（n）中的问题，而没有构建额外的数组。
我相信他的意思是，给定一个数组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];