算法设计手册中数据结构实践的最佳解决方案

Question

这个问题来自于书算法设计手册，3-28。
问题是：

您有一个由 n 个整数组成的无序数组 X。查找包含 n 个元素的数组 M，其中 M_i 是 X 中除 X_i 之外的所有整数的乘积。您不能使用除法，并且可以使用额外的内存。 （提示：存在比 O(n^2) 更快的解决方案。

有人有一些好主意吗？

Answer 1

O(n)解：

1. 计算数组 A，使得 A_i 是 X_1..X_i 的乘积
2. 计算数组 B，使得 B_i 是 X_i..X_n 的乘积（相反，即来自数组索引 n）
3. 然后将 M 计算为 M_i = A_(i-1)*B_(i+1)

使用之前迭代中计算的子积，可以在 O(n) 内计算步骤 1 和 2。

[当然，处理索引转义数组边界的极端情况！]

编辑：为了清楚起见，我提供了下面的完整解决方案

1. 计算数组A为：A_1 = X_1；对于 (2..N) 中的 i：A_i = A_(i-1)*X_i
2. 计算数组B为：B_n = X_n；对于 (N..2) 中的 i：B_i = B_(i+1)*X_i
3. 计算数组M为：M_1 = B_2； M_n = A_(n-1);对于 (2..(N-1)) 中的 i：M_i = A_(i-1)*B_(i+1)

Answer 2

只需使用一个数组和两个循环，一个循环是从前往后，另一个循环是从后到结束。

b[0] =      a[1]*a[2]*a[3]*a[4]
b[1] = a[0]*     a[2]*a[3]*a[4]
b[2] = a[0]*a[1]*     a[3]*a[4]
b[3] = a[0]*a[1]*a[2]*     a[4]
b[4] = a[0]*a[1]*a[2]*a[3]

代码如下：

void solve(int arr[], int len){
    int index = 0;

    // loop from begin to end
    arr_b[0] = 1;
    for (index = 1; index < len; ++index){
        arr_b[index] = arr_b[index - 1]*arr_a[index - 1]; 
    }

    // loop from end to begin
    for (index = len-2; index > 0; --index){
        arr_b[0] *= arr_a[index + 1];
        arr_b[index] *= arr_b[0];
    }
    arr_b[0] *= arr_a[1];
}