有效地乘以(n-1)个数组元素

Question

可能重复:
面试问:给定一个数字数组,返回所有其他数字的产品数组(无分区)

我有两个数组inputArray,每个resultArray都有n元素.
任务是第n个元素resultArray应该inputArray除了第n个元素inputArray(所有元素)之外的所有元素的乘法n-1.
例如.inputArray={1,2,3,4}
那resultArray={24,12,8,6}
很容易......

for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
    if(i != j) resultArray[i] *= inputArray[j];

但问题是复杂性不应超过O(n).
我们也不允许使用除法.
我该如何解决这个问题？

Answer 1

您是否知道奇数乘法是可逆的 - 仅使用乘法？请参阅“黑客之乐”，称为“精确除法”之类的东西。这个技巧也可以扩展到偶数，正如那里所解释的。所以你可以用几次乘法来“除”第 n 个数字 - 因为这是家庭作业，所以我将让你来了解如何做。