你能帮我解决这个问题吗？
您有一个包含 n 个整数的无序数组 X。找到包含 n 个元素的数组 M，其中 Mi 是 X 中除 Xi 之外的所有整数的乘积。你不能使用除法。您可以使用额外的内存。 (提示:存在比 O(n^2) 更快的解决方案。)
基本的 - O(n^2) 和一个使用除法很容易。但我无法找到比 O(n^2) 更快的解决方案。
最佳答案
设 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是数组。
希望清楚:)
关于algorithm - Puzzle.. 求解数组 X 中值的乘积，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4057712/