拼图..解决数组X中值的乘积

Question

能帮我解决这个问题吗？

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

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

Answer 1

让我们left[i]在所有元素的产品X从1..i.让我们right[i]在所有元素的产品X从i..N.您可以通过O(n)以下方式在不分区的情况下计算两者:left[i] = left[i - 1] * X[i]和right[i] = right[i + 1] * X[i];

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

注意:left并且right是数组.

希望很清楚:)