算法设计手册中关于数据结构实践的最优解

Question

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

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

谁有什么好主意?

Answer 1

0 (n)解:

1. 计算数组A，使得A_i是X_1..X_i
2. 计算数组B，使B_i是X_i的乘积…X_n(反向，即从数组索引n)
3. 然后计算M M_i =现代(张)* B_ (i + 1)

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

[当然，要处理下标转义数组边界的极端情况!)

编辑:为了清晰，我在下面提供了完整的解决方案

1. 计算阵列A: A_1 = X_1;for i in (2..N): A_i = A_(i-1)*X_i
2. 计算数组B: B_n = X_n;for i in (N..2): B_i = B_(i+1)*X_i
3. 计算阵列M as: M_1 = B_2;M_n = A_(n-1);for i in (2..(N-1)): 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];
}