报告整数乘积的算法

披露该问题基于 CS 类(class)中的一个问题。不过，希望对其进行扩展。

最初的问题很简单，给定一组 n 个整数，报告 n-1 个整数的 n 个乘积(每次缺少一个不同的 n_i)。它是在线性时间内运行。

例如，一组{1, 2, 3, 4}会报告2 * 3 * 4，1 * 3 * 4、1 * 2 * 4和1 * 2 * 3。

(我能想到的)最简单的解决方案是简单地遍历所有 n 整数并计算它们的乘积 (1 * 2 * 3 * 4 ).然后第二次遍历它们，并使用除法，将总乘积除以每个整数。每次报告解决方案(24/1, 24/2, 24/3, 24/4)。

以上代码在线性时间内工作和运行。教授虽然建议我们也想出一种不用 split 的方法。仍然没有空间限制，只有线性时间限制。我已经考虑过了，但我还是一片空白。有什么建议吗？

最佳答案

您可以先计算一个包含所有领先产品的数组——线性时间:

1 
1 * 2
1 * 2 * 3
1 * 2 * 3 * 4

然后是尾随的秒数——这也是线性时间:

            4
        3 * 4
    2 * 3 * 4
1 * 2 * 3 * 4

任何答案都可以直接找到，或者计算为第一个列表中的一个项目和第二个列表中的一个项目的乘积:

              (2 * 3 * 4)
(1)         *     (3 * 4)
(1 * 2)     *         (4)
(1 * 2 * 3)

关于报告整数乘积的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26129754/