arrays - 数组 SDE 面试问题的恒定空间限制。 AND 对经典面试问题的疑惑

Question

给定一个数组 [a1 To an]，我们必须构造另一个数组 [b1 To bn]，其中 bi = a1*a2*…*an/ai .您只能使用常量空间，时间复杂度为 O(n)。不允许分割。

解决方案的逻辑很简单，从产品中去除bi即可得到结果。然而，当我处理解决这个问题时，我发现自己被困住了。以下是我的疑惑:

根据我的理解，这里的常量空间意味着尽管数组的长度是固定的，但我可以使用的变量数量必须是固定的。其中禁止创建新数组来解决问题。因为在处理不同的数组时，创建新数组会使变量的数量不同。

我已经在网上搜索了大多数解决方案，但是我能找到的所有解决方案都创建了新的数组。
那么，我在这里错过了什么吗？有什么想法吗？非常感谢!

Answer 1

我将使用从 0 到 N-1 的数组索引，因为这就是我们在幕后做事的方式。

你可以像这样重写 bi 的方程:bi = (a0×a1×⋯×ai-1) × (ai+1×ai+2×⋯×an-1)，或者更简洁地像这样:bi = (∏ j=0⋯i-1 aj) × (∏j=i+1⋯n-1 aj)。

(如果您不熟悉它，∏ 类似于 ∑，但它是将项相乘而不是相加。此外，这些公式与您问题中的公式并不完全相同，因为根据您问题中的公式，如果 ai 为零，则 bi 未定义。但是，我将假设意图是取消分子和分母中的 ai，即使它为零。)

反正 ，您可以通过从 0 到 n-1 遍历数组 a 来逐步计算左子积 (∏j=0⋯i-1 aj)。您可以通过从 n-1 到 0 遍历数组 a 来计算正确的子产品 (∏j=i+1⋯n-1 aj)。

因此，解决方案是使用两次传递。

第一遍是从 0 到 N-1。设置每个b[i]到 a[j] 的产品为 0 <= j < i .此传递将 b 数组设置为左子产品。这需要 O(N) 时间和循环计数器的恒定空间。

第二遍是从N-1到0。更新每个b[i]乘以 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.