8

问答题 8 /49

数组乘积
输入:一个长度为n的整数数组input
输出:一个长度为n的整数数组result,满足result[i] = input数组中除了input[i]之外所有数的乘积(假设不会溢出)。比如输入:input = {2,3,4,5},输出result = {60,40,30,24}
程序时间和空间复杂度越小越好。


C/C++:
int *cal(int* input , int n);
Java:
int[] cal(int[] input);


参考答案

int *cal(int* input , int n)  
{  
    int i ;  
    int *result = new int[n];  
    result[0] = 1;  
    for(i = 1 ; i < n ; ++i) 
        result[i] = result[i-1]*input[i-1]; 
    result[0] = input[n-1]; 
    
    for(i = n-2 ; i > 0 ; --i)  
    {  
        result[i] *= result[0];  
        result[0] *= input[i];  
    }  
    return result;  
}