algorithm - Puzzle.. 求解数组 X 中值的乘积

Question

你能帮我解决这个问题吗？

您有一个包含 n 个整数的无序数组 X。找到包含 n 个元素的数组 M，其中 Mi 是 X 中除 Xi 之外的所有整数的乘积。你不能使用除法。您可以使用额外的内存。 (提示:存在比 O(n^2) 更快的解决方案。)

基本的 - O(n^2) 和一个使用除法很容易。但我无法找到比 O(n^2) 更快的解决方案。

Answer 1

设 left[i] 是 1..i 中 X 中所有元素的乘积。设 right[i] 是 i..N 中 X 中所有元素的乘积。您可以通过以下方式在 O(n) 中计算两者而无需除法:left[i] = left[i - 1] * X[i] 和 右[i] = 右[i + 1] * X[i];

现在我们将计算 M:M[i] = left[i - 1] * right[i + 1]

注意:left和right是数组。

希望清楚:)