剑指offer 66 计算数组乘积

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

关键是要想到一种O(N)时间的算法.

对于每一个位置, 他的结果是[他左侧数字的乘积] * [他右侧数字的乘积].

因此我们分别先计算左侧和右侧的和的数组.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* constructArr(int* a, int aSize, int* returnSize){
    *returnSize = 0;
    if(!a) return NULL;
    if(aSize == 0) return NULL;
    *returnSize = aSize;

    int *ret = malloc(sizeof(int) * (*returnSize));
    int *left = malloc(sizeof(int) * (*returnSize));
    ret[aSize - 1] = 1;
    left[0] = 1;
    for(int i = 1; i < aSize; i++)
    {
        left[i] = left[i-1] * a[i-1];
        ret[aSize - 1 - i] =  ret[aSize - i] * a[aSize - i];
    }
    for(int i = 0; i < aSize; i++)
    {
        ret[i] *= left[i];
    }
    free(left);
    
    return ret;
}

时间复杂度: N
空间复杂度: N, 额外的left数组