给你一个数组 [a1 To an]，我们必须构造另一个数组 [b1 To bn] where bi = a1*a2*…*an/ai。您只能使用恒定空间，时间复杂度为 O(n)。不允许划分。
解的逻辑很简单，把产品中的bi去掉就可以得到结果。然而，当我着手解决这个问题时，我发现自己被困住了。这是我的疑问：
根据我的理解，这里的常数空间意味着尽管数组的长度，我可以使用的变量的数量必须是固定的。其中禁止创建新数组来解决问题。因为在处理不同的数组时，创建新数组会使变量的数量不同。
我已经在网上搜索了大多数解决方案，但是我能找到的所有解决方案都创建了新数组。那么，我在这里错过了什么吗？有什么想法吗？非常感谢！
我将使用从 0 到 N-1 的数组索引，因为这就是我们在后台做事的方式。
您可以像这样重写 b i 的等式： b i = (a 0 ×a 1 ×⋯×a i-1 ) × (a i+1 ×a i+2 ×⋯×a n-1 )，或更多简而言之：b i = (∏<sub>j=0⋯i-1 a j ) × (∏<sub>j=i+1⋯n-1 a j )。
（如果您不熟悉它，∏ 就像 ∑，但它会将术语相乘而不是相加。此外，这些公式与您问题中的公式并不完全相同，因为根据您问题中的公式，如果 a i为零，则b i未定义。但是，我将假设其意图是取消分子和分母中的 a i，即使它为零。）
无论如何，您可以通过从 0 到 n-1 遍历数组 a 来递增地计算左子积 (∏<sub>j=0⋯i-1 a j )。您可以通过从 n-1 到 0 遍历数组 a来计算正确的子积 (∏<sub>j=i+1⋯n-1 a j )。
因此解决方案是使用两遍。
第一遍是从 0 到 N-1。将每个设置为forb[i]的乘积。此过程将 b 数组设置为左侧子产品。这需要 O(N) 时间和循环计数器的恒定空间。a[j]0 <= j < i
第二遍是从 N-1 到 0。b[i]通过将其乘以 for 的乘积a[j]来更新每个i < j < N。因此 pass 通过将每个元素乘以适当的右子积来更新 b 数组。这需要 O(N) 时间和恒定空间用于循环计数器和临时。
这是一个 Python 解决方案：
b[0] = 1
for i in range(1, N):
b[i] = b[i - 1] * a[i - 1]
# Now every b[i] is the product of the a[j] where 0 <= j < i.
t = 1
for i in range(N-1, -1, -1):
b[i] = b[i] * t
t *= a[i]
# Now every b[i] is the product of the a[j] where 0 <= j < i
# and the a[j] where i < j <= N-1. This is the desired output.
恒定的空间要求并不禁止创建新数组。这只是意味着您的算法每次运行时都需要使用相同数量的空间。由于该问题要求您构建一个新数组，因此我将展示一个函数，该函数在恒定空间和线性时间内执行此操作。
您仍然可以创建一个新数组。只要确保它是一个恒定的大小。最简单的方法是使其尽可能大。例如，在 C++ 中，您可以使用
int* b = new int[UINT_MAX];
因为数组中使用的最大索引是 UINT_MAX。这是一个既是线性时间、恒定空间又是根据需要构造一个新数组的解决方案。
int* prod(int *a, int len) {
int* b = new int[UINT_MAX];
int tmp = 1;
b[0] = 1;
for (int i = 1; i < len; i += 1) b[i] = b[i - 1] * a[i - 1];
for (int i = len - 1; i >= 0; i -= 1) {
b[i] = b[i] * tmp;
tmp *= a[i];
} // for
return b;
} // prod
函数的约定应该是新数组的大小与输入数组的大小相同（尽管我们偷偷知道它更大）。当然，这不如就地计算有效，但这不是问题所要问的（至少是措辞的方式）。
您可能可以执行以下操作：
/* size = size of the original array*/
/* orgArr = the original array with the numbers*/
int i;
int temp = 1;
int *result = (int *)malloc(sizeof(int) * size);
memset(result, 1, size);
for(i = 0; i < size; i++)
{
result[i] = temp;
temp *= orgArr[i];
}
temp = 1;
for(i= n-1; i >= 0; i--)
{
result[i] *= temp;
temp *= OrgArr[i];
}
空间复杂度 => O(n) 时间复杂度 => O(n)
您可以使用 UINT_MAX 作为结果而不是大小来使其成为一个常量空间。
回顾问题，
天真的方法是使用除法，并计算所有内容，一次，
#!/bin/env ruby #because I can
n = aray.size - 1
prod = 1
0.upto(n) { |x| prod *= aray[x] }
0.upto(n) { |x| bray[x] = (aray[x]==0) ? 0 : prod/aray[x] }
请注意，我使用了 bray[]，但可以轻松地发出结果，或者替换 aray[]
但问题陈述不允许除法。太糟糕了。
因此，我们需要保留原始值，将结果放入 bray[] 中，在这里我们循环遍历 aray[] 两次，从左到右计算乘积，然后从右到左返回，
#!/bin/env ruby #because I can
aray = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ]
bray = [ ]
n = aray.size-1
prod = 1
0.upto(n) { |ndx| bray[ndx] = prod; prod *= aray[ndx]; }
prod = 1
n.downto(0) { |ndx| bray[ndx] *= prod; prod *= aray[ndx]; }
打印结果，
print "aray:\n";
aray.each_index { |ndx| print "[#{ndx}] #{aray[ndx]}\n" }
print "bray:\n";
bray.each_index { |ndx| print "[#{ndx}] #{bray[ndx]}\n" }
这是程序的核心部分。
给定
a[i] 其中 i 的范围从 0 到 n-1
b[i] 其中 i 的范围从 0 到 n-1。
假设 n = 4 用于演示目的
代码从这里开始
int count,sum=1;
for(count = 0; count < n; count++)
{
b[count] = sum;
sum *= a[count];
}
/*
循环计数 = 0
b[0] = 1;
sum = a[0]
循环计数 = 1
b[1] = a[0]
sum = a[0] a[1]
循环计数 = 2
b[2] = a[0] a[1]
sum = a[0] a[1] a[2]
循环计数 = 3
b[3] = a[0] a[1] a[2]
sum = a[0] a[1] a[2] a[3] -- This sum is not used at all
在循环结束时
b[0] = 1;
b[1] = a[0]
b[2] = a[0] a[1]
b[3] = a[0] a[1] a[2]
*/
sum = 1;
for(count = n-1; count >= 0; count--)
{
b[count] *= sum;
sum *= a[count];
}
/*
在 LOOP 开始时
b[3] = a[0] a[1] a[2]
b[2] = a[0] a[1]
b[1] = a[0]
b[0] = 1;
循环计数 = 3
b[3] = a[0] a[1] a[2] -- multiplied with 1 will lead to the same answer
sum = a[3]
循环计数 = 2
b[2] = a[0] a[1] a[3]
sum = a[3] a[2]
循环计数 = 1
b[1] = a[0] a[2] a[3]
sum = a[3] a[2] a[1]
循环计数 = 0
b[0] = a[1] a[2] a[3] -- Multiplied with 1 will lead to the same answer
sum = a[3] a[2] a[1] a[0] -- This sum is not used at all.
在循环结束时
b[0] = a[1] a[2] a[3]
b[1] = a[0] a[2] a[3]
b[2] = a[0] a[1] a[3]
b[3] = a[0] a[1] a[2]
*/